Finding the complexity T(n) = 4T(n/2) + (n^2)*logn using the iteration method

Question

I need to find complexity of this recursion using the iteration method only:

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

I know that you can solve this using the master method and the complexity is (n^2)(logn)^2, but I tried solving it using the iteration method and I got something else:

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

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

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

T(n) = (4^i) * T(n/(2^i)) + 4^(i-1) * (n/(2^(i-1)))^2 * log(n/(2^(i-1)))

After using i = logn I get that the algorithm has a complexity of 2^n.. which is incorrect.

Solution

If you will carefully unwind the recursion, you will get: .

Now the complicated sum becomes

This recursion will exhaust itself when n/2^k = 1 or k = log(n). Substituting it back in the equation you get:

, where c = T(1).

So everything is dominated by n^2 log^2(n) and this is the complexity of your recursion.

P.S. actually no need to approximate to sum, it is easy to calculate it with elementary math.