Master's Theorem — Statement & Applications

Theorem

For $T(n)=aT(n/b)+f(n)$, $a\ge1$, $b>1$:
Let $c=\log_b a$.

• Case 1: $f(n)=O(n^{c-\epsilon})$ → $T(n)=\Theta(n^{c})$ (leaf heavy).
• Case 2: $f(n)=\Theta(n^{c}\log^{k} n)$ → $T(n)=\Theta(n^{c}\log^{k+1} n)$; with $k=0$ → $\Theta(n^{c}\log n)$ (balanced).
• Case 3: $f(n)=\Omega(n^{c+\epsilon})$ + regularity $a f(n/b)\le c' f(n)$ → $T(n)=\Theta(f(n))$ (root heavy).

(i) $T(n)=2T(n/2)+n$

• $c=\log_2 2=1$ → $n^{c}=n$, $f(n)=n=\Theta(n^{c})$ → Case 2 (k=0) → $$T(n)=\Theta(n\log n)$$ (Merge Sort).

(ii) $T(n)=3T(n/2)+n^2$

• $c=\log_2 3 \approx1.585$, $n^{c}=n^{1.585}$, $f(n)=n^2=\Omega(n^{c+\epsilon})$ with $\epsilon\approx0.415$.
• Regularity: $3(n/2)^2=3n^2/4 \le c f(n)$ with $c=3/4<1$ holds → Case 3 → $$T(n)=\Theta(n^2)$$
  Alternatively leaf vs root: root dominates.

(iii) $T(n)=2T(n/2)+n/\log n$

• $c=1$ → $n^{c}=n$, $f(n)=n/\log n = \Theta(n^{c}/\log n)$.
• This is not polynomially smaller ($n^{c-\epsilon}$) nor $\Theta(n^{c})$; it is $n/\text{polylog}$ — gap between cases 1 and 2.
• Master Theorem does NOT apply (fails polynomial gap condition). By recursion tree / Akra-Bazzi:
  $$T(n)=2T(n/2)+n/\log n\;\Rightarrow\; T(n)=\Theta(n\log\log n)$$
  Proof sketch: $T(n)=n\sum_{i=0}^{\log n -1} 1/(\log n -i)=n H_{\log n}=n\cdot\Theta(\log\log n)$.
• If forced into extended Case 2 ($k=-1$), some extensions give $\Theta(n\log\log n)$.

Summary: (i) $\Theta(n\log n)$ Case2, (ii) $\Theta(n^2)$ Case3, (iii) Gap case — $\Theta(n\log\log n)$, master not applicable in strict form.