Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$ 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 all three common methods: iteration, master theorem and substitution.
It is highly likely that this kind of recurrence equation will be in my test in two days. Thank you very much in advance!
 A: You're likely to get a comment about asking multiple questions as one big one, but to get you started, I'll do an iterative expansion.
Let $n=2^k$, since strictly speaking those are the only values for which your recurrence makes sense. Then your recurrence takes the form
$$
T(2^k) = 2^2T(2^{k-1})+2^{2k}k
$$
Now let's iterate
$$\begin{align}
T(2^k) &= 2^2[T(2^{k-1})]+2^{2k}k \\
       &= 2^2[2^2T(2^{k-2})+2^{2(k-1)}(k-1)]+2^{2k}k\\
       &\qquad= 2^4T(2^{k-2})+2^{2k}(k-1)+2^{2k}k\\
       &= 2^4[2^2T(2^{k-3})+2^{2(k-2)}(k-2)]+2^{2k}(k-1)+2^{2k}k\\
       &\qquad= 2^6T(2^{k-3})+2^{2k}(k-2)+2^{2k}(k-1)+2^{2k}k
\end{align}$$
and the general pattern appears to be
$$\begin{align}
T(2^k) &= 2^{2j}T(2^{k-j})+2^{2k}(k-j+1)+2^{2k}(k-k+2)+\cdots+2^{2k}k\\
       &= 2^{2j}T(2^{k-j})+2^{2k}((k-j+1)+(k-j+2)+\cdots k)
\end{align}$$
assuming we've correctly guessed the pattern, we let $j=k$ and obtain
$$
T(2^k)= 2^{2k}T(2^0)+2^{2k}(1+2+3+\cdots k)=(2^k)^2+(2^k)^2\frac{k(k+1)}{2}
$$
Finally, recall that we set $n=2^k$ so $k=\lg n$ so we have the solution
$$
T(n) =n^2+n^2\frac{\lg n(\lg n+1)}{2}=\Theta(n^2\lg^2n)
$$
Now all you have to do is complete the remaining two parts. (grins)
A: We can compute exact formulas for your recurrence and not just at powers of two. Suppose we first solve the recurrence
$$T(n) = 4 T(\lfloor n/2\rfloor) +  n^2 (1+\lfloor \log_2 n\rfloor)$$
with $T(0)=0.$
Then let $$n= \sum_{k=0}^{\lfloor \log_2 n\rfloor} d_k 2^k$$ be the binary representation of $n$ and unroll the recursion to get the following exact formula for $T(n):$
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n\rfloor} 4^j
(1+\lfloor \log_2 n\rfloor -j)
\left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^{k-j} \right)^2
\\= \sum_{j=0}^{\lfloor \log_2 n\rfloor} 
(1+\lfloor \log_2 n\rfloor -j)
\left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^k \right)^2.$$
Now to get an upper bound on this consider a string of one digits, which gives
$$T(n)\le  \sum_{j=0}^{\lfloor \log_2 n\rfloor} 
(1+\lfloor \log_2 n\rfloor -j)
\left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} 2^k \right)^2
= \sum_{j=0}^{\lfloor \log_2 n\rfloor} 
(1+\lfloor \log_2 n\rfloor -j) (2^{1+\lfloor \log_2 n\rfloor}-2^j)^2
\\ = \sum_{j=1}^{1+\lfloor \log_2 n\rfloor} 
j (2^{1+\lfloor \log_2 n\rfloor}-2^{1+\lfloor \log_2 n\rfloor-j})^2
=2^{2(1+\lfloor \log_2 n\rfloor)}
\sum_{j=1}^{1+\lfloor \log_2 n\rfloor} j \times (1-2^{-j})^2.$$
The dominant term in the sum is $j$ which contributes $\sum_{j=1}^{1+\lfloor \log_2 n\rfloor} j$ to give
$$\frac{1}{2} 2^{2(1+\lfloor \log_2 n\rfloor)} 
(1+\lfloor \log_2 n\rfloor)(2+\lfloor \log_2 n\rfloor).$$
For a lower bound consider a one followed by zeros to obtain
$$T(n)\ge  \sum_{j=0}^{\lfloor \log_2 n\rfloor} 
(1+\lfloor \log_2 n\rfloor -j)
2^{2\lfloor \log_2 n\rfloor}
= 2^{2\lfloor \log_2 n\rfloor}\sum_{j=1}^{1+\lfloor \log_2 n\rfloor} j.$$
Simplifying the sum term we get
$$\frac{1}{2} 2^{2\lfloor \log_2 n\rfloor} 
(1+\lfloor \log_2 n\rfloor)(2+\lfloor \log_2 n\rfloor)$$
which is exact this time compared to the upper bound which was asymptotic.
The conclusion is that by taking the two bounds together we obtain
$$T(n)\in\Theta\left(2^{2\lfloor \log_2 n\rfloor}
(1+\lfloor \log_2 n\rfloor)(2+\lfloor \log_2 n\rfloor)\right)
= \Theta\left(n^2 \times \log^2 n\right).$$
A variety of Master Theorem computations can be found at this MSE link. In fact there is another very similar solution to this problem at this MSE link II.
