Solving T(n) = 4T(n/2)+n²

Question

I am trying to solve a recurrence using substitution method. The recurrence relation is:

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

My guess is T(n) is Θ(nlogn) (and i am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that T(n)<=cn²logn, but that did not work.

I got T(n)<=cn²logn+n². Then I tried to show that, if T(n)<=c₁n²logn-c₂n², then it is also O(n²logn), but that also didn't work and I got T(n)<=c₁n²log(n/2)-c₂n²+n²`.

How can I solve this recurrence?

Solution 1

T(n) = 4T(n/2) + n2
     = n2 + 4[4T(n/4) + n²/4]
     = 2n2 + 16T(n/4) 
     = ... 
     = k⋅n2 + 4kT(n/2k) 
     = ...

The process stops when 2k reaches n.
⇒ k = log2n
⇒ T(n) = O(n2logn)

Solution 2

You can rewrite your equation in a non-recursive form

Your recursive equation is pretty simple: every time you expand T(n/2) only one new term appears. So in the non-recursive form you'll have a sum of quadratic terms. You only have to show that A(n) is log(n) (I leave it to you as an easy exercise).