Solving a recurrence T(n) = 2T(n/2) + n^4
- by user563454
I am studying using the MIT Courseware and the CLRS book Introduction to Algorithms.
Solving recurrence T(n) = 2T(n/2) + n4 (page 107)
If I make a recurrence tree I get:
level 0 n^4
level 1 2(n/2)^4
level 2 4(n/4)^4
level 3 8(n/8)^4
The tree has lg(n) levels. Therefore the recurrence is
T(n) = Theta(lg(n)n^4))
But, If I use the Master method I get.
Apply case 3: T(n) = Theta(n^4)
If I apply the substitution method both seem to hold. Which one is ri?
