Give an asymptotic upper bound for $T(n) = 4T(\frac{n}{2}) + n^2log_2n$

Question

Give an asymptotic upper bound for $$T(n) = 4T(\frac{n}{2}) + n^2log_2n$$ Using the recursion tree method, I obtain $$\sum_{i=0}^{log_2n - 1} \frac{n}{2^i}log_2\frac{n}{2^i} + n^2\theta(1)$$ Not sure how to solve this summation.

Answer 1

From

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

making $\mathbb{T}(\cdot) = T(2^{(\cdot)}),\ \ z = \log_2 n$ we have

$$ \mathbb{T}(z) = 4\mathbb{T}(z-1)+z 4^z $$

This recurrence has the solution

$$ \mathbb{T}(z) = \frac 12 z(z+1)4^z+C_0 4^{z-1} $$

and backtracking we have

$$ T(n) = C_1n^2+\frac 12(\log_2 n+1)n^2\log_2 n $$

then

$$ T(n) \approx \Theta\left((n\log_2 n)^2\right) $$

Answer 2

In $\sum_{i=0}^{log_2n - 1} \frac{n}{2^i}log_2\frac{n}{2^i} + n^2\theta(1) $, let $n = 2^m$.

This is

$\begin{array}\\ \sum_{i=0}^{m - 1} 2^{m-i}\log_2(2^{m-i}) + 2^{2m}\theta(1) &=2^m\sum_{i=0}^{m - 1} (m-i) 2^{-i} + 2^{2m}\theta(1)\\ &=2^m(\sum_{i=0}^{m - 1} m 2^{-i}-\sum_{i=0}^{m - 1}i 2^{-i}) + 2^{2m}\theta(1)\\ &=2^m(m(1-2^{-m})-\dfrac{1+O(2^{-m})}{(1-\frac12)^2}) + 2^{2m}\theta(1)\\ &=2^m(m(1-2^{-m})-4+O(2^{-m})) + 2^{2m}\theta(1)\\ &=m2^m + 2^{2m}\theta(1)\\ &=\Theta(n^2)\\ \end{array} $

So the sum is small compared to the $n^2$ term.