Master Theorem Applications

General Form: $T(n)=aT(n/b)+f(n)$, $a\ge1$, $b>1$, $f(n)$ asymptotically positive.
Let $n^{\log_b a}$ be the watershed.

• Case 1: $f(n)=O(n^{\log_b a -\epsilon})$ for $\epsilon>0$ → $T(n)=\Theta(n^{\log_b a})$.
• Case 2: $f(n)=\Theta(n^{\log_b a}\log^k n)$ → $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$; special $k=0$: $\Theta(n^{\log_b a}\log n)$.
• Case 3: $f(n)=\Omega(n^{\log_b a+\epsilon})$ and regularity $a f(n/b)\le c f(n)$ for $c<1$ → $T(n)=\Theta(f(n))$.

(i) $T(n)=4T(n/2)+n^3$

• $a=4$, $b=2$ → $n^{\log_b a}=n^{\log_2 4}=n^2$.
• $f(n)=n^3=\Omega(n^{2+1})$ with $\epsilon=1$.
• Regularity: $4(n/2)^3 =4 n^3/8 = n^3/2 \le c n^3$ with $c=1/2<1$ ✓
• Case 3 → $$T(n)=\Theta(f(n))=\Theta(n^3)$$

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

• $a=1$, $b=2$ → $n^{\log_b a}=n^0=1$.
• $f(n)=2^n$ is exponential, not polynomial; $2^n = \Omega(n^{\epsilon})$ for any $\epsilon$, dominated by $f$.
• Although $f(n)=2^n = \Omega(n^{0+\epsilon})$, regularity holds: $1\cdot2^{n/2} \le c 2^n$ for large $n$ ($c=1/2$) as $2^{n/2}/2^n=2^{-n/2}\to0$.
• This fits Case 3 (generalized interpretation) where $f$ dominates polynomially. Hence $$T(n)=\Theta(f(n))=\Theta(2^n)$$

Note: Strict Master theorem in many textbooks requires $f$ polynomial; for exponential $f$, the theorem still yields $T(n)=\Theta(2^n)$ because $n^{\log_b a}=O(f(n))$ and regularity holds; formally the answer is exponential dominated, not $\Theta(1)$. Some state "Master theorem not applicable (f not polynomial)" but via extension the bound is $\Theta(2^n)$; if insisting on polynomial $f$ condition, declare not applicable, recurrence solves to $\Theta(2^n)$ by recursion tree: $T(n)=2^n+2^{n/2}+2^{n/4}+\dots+1 =\Theta(2^n)$.