Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

Question

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

Answer 1

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)$.