# Solving $T(n)=4T(n/2)+n^2$

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T(n/2)+n^2$$ My guess is $T(n)$ is $\Theta(n\log n)$ (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)\le cn^2\log n$ but that did not work, I got $T(n)\le cn^2\log n+n^2$.

I then tried to show that, if $T(n)\le c_1 n^2\log n-c_2 n^2$, then it is also $\mathcal O(n^2\log n)$, but that also did not work and I got $T(n)\le c_1n^2\log(n/2)-c_2 n^2+n^2$.

What trick can I use to show that? Thanks.

• the solution should be O(n^2logn). – sukunrt Mar 3 '13 at 13:46
• Please have a look at our reference questions, especially under the section "Asymptotics". – Paresh Mar 3 '13 at 15:34
• Also, did you mean $\Theta(n^2\log n)$ instead? Since you are trying to show $T(n) \le cn^2\log n$ later. – Paresh Mar 3 '13 at 15:36
• See Solving or approximating recurrence relations for sequences of numbers, as hinted by @Paresh. – Juho Mar 3 '13 at 15:38
• It seems I forgot to link the collection of reference pages. Thanks @Juho – Paresh Mar 3 '13 at 15:40

$T(n) \leq c_1 n^2 \lg n- c_2 n$ and you will be able to show by substitution that $T(n) = O(n^2 \lg n)$ for appropriate values of the constants ($c_2 > 1$ and $c_1$ big enough to correctly handle the initial conditions).
That's a recurrence of the form: $T(n)=aT(n/b)+f(n)$. In your case $a=4$, $b=2$, and $f(n)=n^2$. This is case 2 of the master theorem. It follows that $T(n)=\Theta(n^2\log n)$.