2
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.