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

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?

• The definitive version of the master theorem can be found on Wikipedia. I suggest ignoring all other sources. Commented Feb 10, 2021 at 8:51
• The solution to $T(n) = 4T(n/2) + n^2\log n$ is indeed $T(n) = \Theta(n^2\log^2 n)$. Commented Feb 10, 2021 at 8:52

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

• Thank you very much. I did the same recursion but I made an algebra mistake. Now I understand.
– Dan
Commented Feb 10, 2021 at 14:51