Asymptotic Analysis & Recurrences
Asymptotic Analysis & Recurrences
Algorithm analysis quantifies resource usage — time and space — as functions of input size $n$. Big-O notation $O(g(n))$ captures worst-case growth, $\Omega$ captures best-case, and $\Theta$ captures tight bounds. Recurrences arise from divide-and-conquer algorithms; the Master theorem solves them in closed form.
Big-O Notation
$f(n)=O(g(n))$ if $\exists c>0,n_0$ such that $f(n)\leq c\cdot g(n)$ for all $n\geq n_0$. Similarly: $f=\Omega(g)$ iff $g=O(f)$; $f=\Theta(g)$ iff $f=O(g)$ and $f=\Omega(g)$. Hierarchy: $O(1)\subset O(\log n)\subset O(n)\subset O(n\log n)\subset O(n^2)\subset O(2^n)\subset O(n!)$. Note: $O$ hides constants — a $1000n$ algorithm beats $n^2$ eventually.
Master Theorem
For recurrences $T(n)=aT(n/b)+f(n)$ with $a\geq 1$, $b>1$: let $c=\log_b a$. (1) If $f(n)=O(n^{c-\epsilon})$: $T=\Theta(n^c)$. (2) If $f(n)=\Theta(n^c\log^k n)$: $T=\Theta(n^c\log^{k+1}n)$. (3) If $f(n)=\Omega(n^{c+\epsilon})$ and regularity holds: $T=\Theta(f(n))$. Mergesort: $T=2T(n/2)+O(n)$, $c=1$, case 2: $T=O(n\log n)$.
Example 1
Solve $T(n)=4T(n/2)+n$.
Solution: $a=4,b=2,c=\log_2 4=2$. $f(n)=n=O(n^{2-1})$, case 1: $T(n)=\Theta(n^2)$.
Example 2
Solve $T(n)=2T(n/2)+n\log n$.
Solution: $a=b=2$, $c=1$. $f(n)=n\log n=\Theta(n^1\log^1 n)$, case 2 with $k=1$: $T(n)=\Theta(n\log^2 n)$.
Practice
- Prove $\sum_{k=0}^{\log n}2^k=2n-1$ and use it to derive $T(n)=2T(n/2)+n=O(n\log n)$ by expansion.
- Show that the binary search recurrence $T(n)=T(n/2)+O(1)$ gives $T(n)=O(\log n)$.
- Solve $T(n)=T(n-1)+n$ and $T(n)=T(\sqrt{n})+1$ using substitution.
- Prove the recurrence for Strassen's matrix multiplication $T(n)=7T(n/2)+O(n^2)$ gives $T=O(n^{2.807})$.
Show Answer Key
1. Geometric series: $\sum_{k=0}^{\log n}2^k = 2^{\log n+1}-1 = 2n-1$. Expansion of $T(n)=2T(n/2)+n$: at level $k$, there are $2^k$ subproblems of size $n/2^k$, each costing $n/2^k$ work → total work per level $= n$. There are $\log n +1$ levels, so $T(n) = n(\log n +1) = O(n\log n)$.
2. Binary search: $T(n) = T(n/2)+O(1)$. Expand: $T(n)=T(n/2^k)+kO(1)$. Terminates at $k=\log_2 n$ → $T(n)=T(1)+O(\log n)=O(\log n)$. Alternatively, by Master Theorem: $a=1, b=2, f(n)=O(1)=O(n^{\log_b a})=O(n^0)$, Case 2 → $T=O(\log n)$.
3. $T(n)=T(n-1)+n$: expand $T(n)=T(0)+\sum_{k=1}^n k = n(n+1)/2 = O(n^2)$. For $T(n)=T(\sqrt{n})+1$: let $n=2^m$, so $T(2^m)=T(2^{m/2})+1$. Set $S(m)=T(2^m)$: $S(m)=S(m/2)+1=O(\log m)$. Back-substitute: $T(n)=O(\log\log n)$.
4. Strassen: $a=7, b=2, f(n)=O(n^2)$. $\log_2 7 \approx 2.807$. Since $f(n)=O(n^{\log_b a - \epsilon})$ with $\epsilon \approx 0.807$ (Case 1 of Master Theorem): $T(n) = O(n^{\log_2 7}) = O(n^{2.807})$. ✓