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?

Plimsoll

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⁴).

Monaxial

ah yes, I see my mistake. Nice explanation on why it is less than 2n^4. Thanks – Plimsoll

Answer 2

With recursion it is Θ(n^4)

T(n) = 2*T(n/2) + n^4 
T(n) = 2( 2*T(n/4) + (n/2)^4) + n^4 = 4*T(n/4) + 2*(n/2)^4 + n^4
T(n) = 4(2*T(n/8) + (n/4)^4) + 2*(n/2)^4 + n^4 = 8*T(n/8) + 4*(n/4)^4 + 2(n/2)^4 + n^4

T(n) = 8*T(n/8) + n^4*(1 + 1/(2^3) + 1/(2^6))
...

T(n) = 2^k*T(n/(2^k)) + n^4*(1+ 1/(2^3) + 1/(2^6) + 1/(2^9)...+ 1/((2^(k-1))^3)

We know T(1) = 1

n = 2^k so k = log2(n) Then

T(n) = n*T(1) + n^4*( 1 - (1/(2^3))^k)/(1-1/8)

T(n) = n + (8/7)*n^4*(1 - n^(-3))

T(n) = n + (8/7)*(n^4 - n)

T(n) = (8/7)*n^4 - (1/7)*n


Θ(T(n)) = Θ((8/7)*n^4 - (1/7)*n)
Θ(T(n)) = Θ(n^4)

it is Θ(n^4)

Antiserum

Answer 3

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)

Teaching

Answer 4

By Master Theorem

a=2, b=2, f(n)=n^4

First step - Calculate n^(log a to base b) => n(log 2 to base 2) = n*1 = n Second Step - Is f(n)> First step result => n^4> n => YES This means use Case 3 of Master Theorem.

Third step - Check Regularity Condition

a. f(n/b) <= c. f(n) where c>1 
a(n/b) . log(n/b) <= c. f(n)
2.(n/2) . log(n/2) <= c. n^4
n.log(n/2) <= c.n^4

Yes, Regularity condition is met, so our solution must be.

T(n) =theta (f(n)) = theta(n^4)

Jarvis