patternMinor
Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$
Viewed 0 times
logapplymastertheoremdoes
Problem
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?
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?
Solution
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).
\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).
Context
StackExchange Computer Science Q#135313, answer score: 2
Revisions (0)
No revisions yet.