# Solving $T(n)=4T(\frac{n}{2})+n^2$

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+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)\leq cn^{2}\log n$ but that did not work, I got $T(n)\leq cn^{2}\log n+n^{2}$. Then I tried to show that, if $T(n)\leq c_{1}n^{2}\log n-c_{2}n^{2}$, then it is also $O(n^{2}\log n)$, but that also did not work and I got $T(n)\leq c_{1}n^{2}\log(n/2)-c_{2}n^{2}+n^{2}$. What trick can I do to show that? Thanks

-
What happens when $n$ is odd or just not a power of $2$? –  Dennis Gulko Mar 3 '13 at 12:37
We can ignore these cases –  copy_constructor Mar 3 '13 at 12:39
In that case perhaps it would be better to write $t(2n)=4t(n)+n^{2}$? –  Daniel Littlewood Mar 3 '13 at 12:42
Its probably $T(\lfloor \frac{n}{2} \rfloor)$, but the floor doesn't make a difference when analysing asymptotic behaviour. –  Ivan Loh Mar 3 '13 at 12:48

If $T(\frac{n}{2}) \leq c(\frac{n}{2})^2\log_2(\frac{n}{2})+T(1)$, then \begin{align} T(n)=4T\left(\frac{n}{2}\right)+n^2 & \leq 4c\left(\frac{n}{2}\right)^2\log_2\left(\frac{n}{2}\right)+4T(1)+n^2 \\ &=cn^2\log_2(n)-cn^2+4T(1)+n^2 \\ &\leq cn^2\log_2(n)+T(1) \end{align} for $c \geq 1+3T(1)$.

-
Thanks, but i did not understand how you get -cn^2 at the 3rd line? –  copy_constructor Mar 3 '13 at 13:01
i get it now, thank you! –  copy_constructor Mar 3 '13 at 13:05