Solving a recurrence T(n) = 2T(n/2) + n^4

Question

I am studying using the MIT Courseware and the CLRS book Introduction to Algorithms.

I am currently trying to solve the recurrence (from page 107)

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

If I make a recurrence tree, I get:

Level 0: n⁴

Level 1 2(n/2)⁴

Level 2 4(n/4)⁴

Level 3 8(n/8)⁴

The tree has lg(n) levels. Therefore I think that the recurrence should be

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

But, If I use the master theorem, I get that

T(n) = Θ(n⁴)

Clearly both of these can't be right. Which one is correct? And where did I go wrong with my reasoning?

Answer 1

The second one looks correct. Notice that your recurrence tree looks like

n⁴ + 2(n/2)⁴ + 4(n/4)⁴ + ... + 2ⁱ (n / 2ⁱ)⁴

But 2(n/2)⁴ ≠ n⁴, because (n/2)⁴ = n⁴ / 16, and so 2(n/2)⁴ = n⁴/8. In fact, if you work out the math, you get that the work being done at level i is given by

n⁴ / (2^-3i)

So we get (1 + 1/8 + 1/64 + 1/512 + ... ) n⁴, which can be shown to be less than 2n⁴. So your function is Θ(n⁴).