Solving T(n)=4T(n/2)+n with iterative methode

Question

I am trying to solve a recurrence using iterative method. I know the solution should be θ(n^2) but I'm not able to solve it with the iterative method.

This is how far I got:

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

I dont know how to calculate the sum. I hope someone can help me.

Thanks in advance!

Answer 1

Let's define k such that 2^k = n (^ stands for raising into power). So we have

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

as

T(2^k) = 2^2 * T(2^(k-1)) + 2^k

Let's unwind it:

T(2^k) = 2^2 * T(2^(k-1)) + 2^k =
       = 2^4 * T(2^(k - 2)) + 2^(k + 1) + 2^k =
       = 2^6 * T(2^(k - 3)) + 2^(k + 2) + 2^(k + 1) + 2^k =
       = 2^8 * T(2^(k - 4)) + 2^(k + 3) + 2^(k + 2) + 2^(k + 1) + 2^k = 
         ...
       = T(0) * (2^(2 * k) + ... + 2^(k + 2) + 2^(k + 1) + 2^k) =
       = T(0) * (2^k * (2^k + 2^(k - 1) + ... + 4 + 2 + 1)) = 
       = T(0) * (2^k * (2 * 2^k - 1))  

Time to return back from k to n; since we have 2^k = n:

T(n) = T(0) * n * (2 * n - 1)

Having close formula for T(n) we can easily compute θ:

    θ(T(0) * n * (2 * n - 1)) = 
  = T(0) * θ(n * (2 * n - 1)) =
  = 2 * T(0) * θ(n^2) =
  = θ(n^2)