HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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?

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

Context

StackExchange Computer Science Q#135313, answer score: 2

Revisions (0)

No revisions yet.