1
$\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$ – Yuval Filmus Feb 10 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$ – Yuval Filmus Feb 10 at 8:52
0
$\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$ – RAN LIU Feb 10 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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