# Recurrence – Substitution

Find the asymptotic tight bound in

$$T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n.$$

where $\log n= \log _{2}n$ and $T(1) = 1$.

I should solve this using substitution method. I used $n = 2^{k}$, $T(2^{k})=4T(2^{k-1}) + 2^{2k}k$ as Rick and Marko showed me here.

And then I tried to "do the substitution" but it has no visible pattern. I computed other exercises but they were pretty straightforward. Probably I don't understand this method very much even if I googled a lot of materials they contain very easy examples but I have big troubles with the $n^{2}\log n$ part. Any hints, please? (And recommendations of literature too, please.)

Thank you very much in advance. I really need to understand this to pass my exam.

Let $S_k=4^{-k}T(2^k)$, then $S_k=S_{k-1}+k$ for every $k\geqslant1$ and $S_0=1$ hence $S_k=\sum\limits_{i=1}^ki=\frac{k(k+1)}2$. Thus, $T(2^k)=4^k\frac{k(k+1)}2=\Theta((2^kk)^2)$ and, although nothing allows to deduce this, users asking this kind of question on the site seem to consider this is enough to show that $$T(n)=\Theta((n\log n)^2).$$