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

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:

T(n) = 4T(n/2) n
T(n) = 4(4T(n/4) n/2) n
T(n) = 4(4(4T(n/8) n/4) n/2) n

$4^{i}*T(\frac{n}{2^{i}}) \sum ?$

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

Thanks in advance!

CodePudding user response：

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

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

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)

CodePudding user response：

You can approximate it easily by same way you have done:

T(n) = 4T(n/2) n                  
T(n) = 4(4T(n/4) n/2) n         =  4^2 T(n/4)       2n   n
T(n) = 4(4(4T(n/8) n/4) n/2) n  =  4^3 T(n/8)       4n   2n   n
                                  |--first part--|--second part--|

At first, since the iteration halves each time, then this iteration happens log(n) turns at max.

Now for the first part, after ith turn is 4^i, so it will be from O(4^log(n)) = O(n^2).

For the second part, it is a geometric serie n 2n 4n 8n.... n*2^i=n*(2^(i 1)-1). So its amortized time for log(n) turn will be O(n*2^log(n))=O(n^2).

Since both part is O(n^2) and they are summed up, the amortized time of total is also O(n^2).