Problem set: recurrences & asymptotics

◈ 5 cards

Nine worked exam-style recurrences across all three methods, the master-theorem traps, and an empirical confirmation that T(n)=2T(n/2)+n is exactly n lg n + n.

The most-examined skill in the course

AU's exam nearly always asks you to solve a recurrence you have not seen and to prove or classify an asymptotic bound. This is a mechanical skill — drill it until you can do each of the nine below without hesitation.

Master-theorem classifications

Watershed $W = n^{l o g_{b} a}$ ; compare $f$ to $W$ .

$T (n) = 4 T (n /2) + n$ . $W = n^{l o g_{2} 4} = n^{2}$ ; $f = n = O (n^{2 - ε})$ ⟶ case 1 ⟶ $Θ (n^{2})$ .
$T (n) = 4 T (n /2) + n^{2}$ . $W = n^{2}$ ; $f = n^{2} = Θ (W)$ ⟶ case 2, $k = 0$ ⟶ $Θ (n^{2} l g n)$ .
$T (n) = 4 T (n /2) + n^{3}$ . $W = n^{2}$ ; $f = n^{3} = Ω (n^{2 + ε})$ , regularity holds ( $4 (n /2)^{3} = \frac{1}{2} n^{3} \leq c n^{3}$ ) ⟶ case 3 ⟶ $Θ (n^{3})$ .
$T (n) = 2 T (n /2) + n l g n$ . $W = n$ ; $f = n l g n = Θ (n l g^{1} n)$ ⟶ case 2, $k = 1$ ⟶ $Θ (n l g^{2} n)$ . (the trap: NOT n lg n)
$T (n) = T (n /2) + 1$ . $W = n^{l o g_{2} 1} = n^{0} = 1$ ; $f = 1 = Θ (W)$ ⟶ case 2, $k = 0$ ⟶ $Θ (l g n)$ . (binary search)
$T (n) = 7 T (n /2) + n^{2}$ (Strassen). $W = n^{l o g_{2} 7} \approx n^{2.807}$ ; $f = n^{2} = O (n^{2.807 - ε})$ ⟶ case 1 ⟶ $Θ (n^{l g 7})$ .

Recursion tree / substitution (master theorem doesn't apply)

$T (n) = T (n - 1) + n$ . Not a master recurrence (subtracts, not divides). Unroll: $n + (n - 1) + \dots + 1 = \frac{n ( n + 1 )}{2} = Θ (n^{2})$ .
$T (n) = T (n - 1) + 1 = Θ (n)$ ; $T (n) = 2 T (n - 1) + 1 = Θ (2^{n})$ . (subtract-one recurrences: linear vs exponential depending on the branching factor)
$T (n) = T (n /3) + T (2 n /3) + n$ . Unequal split — master theorem can't touch it. Every level sums to $\leq n$ ; the longest path is $lo g_{3/2} n$ levels ⟶ $Θ (n l g n)$ .

The substitution trap to never fall into

Proving $T (n) = 2 T (n /2) + n = O (n)$ by guessing $T (n) \leq c n$ : the step gives $2 (c \frac{n}{2}) + n = c n + n$ , which is not $\leq c n$ . The bound $O (n)$ is simply false here (the true answer is $Θ (n l g n)$ ) — but students often 'rescue' it by writing $\leq c n + n = O (n)$ , silently absorbing the $+ n$ into the $O$ . You may never fold the driving term into the hypothesis constant. The induction must reproduce the same $c n$ exactly.

Empirical check

$T (n) = 2 T (n /2) + n$ with $T (1) = 1$ has the exact closed form $T (n) = n l g n + n$ . So $T (n) / (n l g n) = 1 + 1/ l g n$ , which decreases toward 1 as $n$ grows — the lower-order $+ n$ term fading next to $n l g n$ is exactly what $Θ (n l g n)$ predicts. The exercise below shows that ratio converging.

Compare f to the watershed W = n^(log_b a); the comparison picks the case.