Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$

Question

Based on CLRS Theorem 4.1, master theorem doesn't apply to $T(n) = 4T(n/2) + n^2 \log n$. However, I saw the 4th condition of master theorem on slides of Bourke.

If $f(n)=\Theta(n^{\log_ba}\log^kn)$, then $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$. So $T(n)=3T(n/3)+n\log n$ can apply to case #2, see for example this question.

With the same logic, $T(n) = 4T(n/2) + n^2 \log n$ should be $T(n) = \Theta(n^2\log^2n)$. But it's actually $T(n) = \Theta(n^2\log n)$. Is there anything wrong of my thinking?

Answer 1

You can expand the recurrence $T(n) = 4T(n/2) + n^2 \log n$ directly: \begin{align} T(n) &= n^2 \log n + 4T(n/2) \\ &= n^2 \log n + 4(n/2)^2 \log(n/2) + 16T(n/4) \\ &= n^2 \log n + 4(n/2)^2 \log(n/2) + 16(n/4)^2 \log(n/4) + 64T(n/8) \end{align} and so on. We can simplify the terms: they are $n^2 \log n$, $n^2 \log(n/2) = n^2 (\log n - 1)$, $n^2\log (n/4) = n^2(\log n - 2)$, and so on. Unrolling the recurrence all the way gives \begin{align} T(n) &= n^2 (\log n + \log (n/2) + \cdots + \log(n/(n/2)) + 4^{\log n}T(1) \\ &= n^2 \sum_{k=1}^{\log n} k + n^2 T(1) \\ &= \frac{1}{2} n^2 \log n(\log n - 1) + n^2 T(1) \\ &= \Theta(n^2\log^2 n). \end{align}

This is also what the master theorem gives (case 2 in the Wikipedia version).