Решение повторения T (n) = 2T (n / 2) + n ^ 4

Я изучаю, используя MIT Courseware и книгу CLRS Введение в алгоритмы.

В настоящее время я пытаюсь решить повторение (со страницы 107)

T (n) = 2T (n / 2) + n ⁴

Если я сделаю дерево повторений, я получаю:

Уровень 0: n ⁴

Уровень 1 2 (n / 2) ⁴

Уровень 2 4 (n / 4) ⁴

Уровень 3 8 (n / 8) ⁴

В дереве есть lg (n) уровней. Поэтому я думаю, что повторение должно быть

T (n) = Θ (n ⁴ lg n)

Но, если я использую основную теорему, Я понимаю, что

T (n) = Θ (n ⁴ )

Очевидно, оба из них не могут быть правильными. Который правильный? И где я ошибся в своих рассуждениях?