Solving a recurrence T(n) = 2T(n/2) + n^4
Solution 1
The second one looks correct. Notice that your recurrence tree looks like
n4 + 2(n/2)4 + 4(n/4)4 + ... + 2i (n / 2i)4
But 2(n/2)4 ≠ n4, because (n/2)4 = n4 / 16, and so 2(n/2)4 = n4/8. In fact, if you work out the math, you get that the work being done at level i is given by
n4 / (2-3i)
So we get (1 + 1/8 + 1/64 + 1/512 + ... ) n4, which can be shown to be less than 2n4. So your function is Θ(n4).
Solution 2
You can use the master theorem here directly.
This equation fits in case 1 of master theorem where log (a) base b < f( n)
a : Number of recurrence b : Number of subparts
log a base b = log 2 base 2 = 1 < n^4
Therefore by masters theorem, T(n) = theta(f(n)) = theta(n^4)
huherto
Updated on July 05, 2022Comments
-
huherto almost 2 years
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) + n4
If I make a recurrence tree, I get:
Level 0: n4
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 I think that the recurrence should be
T(n) = Θ(n4 lg n)
But, If I use the master theorem, I get that
T(n) = Θ(n4)
Clearly both of these can't be right. Which one is correct? And where did I go wrong with my reasoning?
-
huherto over 13 yearsah yes, I see my mistake. Nice explanation on why it is less than 2n^4. Thanks