Recurrences and analysis tools
Introduced
Vocabulary
| English | Meaning |
|---|---|
| algorithm design and analysis | algorithm design and analysis |
| recurrence/rɪˈkʌrəns/ | recurrence |
| recursion tree | recursion tree |
The tree is the analysis
- Algorithm design and analysis prices a design before writing it. A recurrence states a recursive algorithm's cost in terms of smaller inputs: $T(n) = 2T(n/2) + \Theta(n)$. The recursion tree draws it: level $i$ has $2^i$ nodes of $n/2^i$, every level costs $\Theta(n)$, the depth is $\log_2 n$ — so $T(n) = \Theta(n \log n)$.
{exercise:uni-cs1001-tree}
Practice
For T(n) = 2T(n/2) + n, one tree level costs —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Level i has 2^i nodes of n/2^i: the product is n at every level.
The master method, one line each
- For $T(n) = aT(n/b) + f(n)$, compare $f(n)$ with $n^{\log_b a}$ (the leaf total). Leaves dominate: $\Theta(n^{\log_b a})$. Balanced: $\Theta(f(n)\log n)$. Root dominates: $\Theta(f(n))$.
- Course cases: $2T(n/2) + n \to n\log n$; $T(n/2) + 1 \to \log n$; $4T(n/2) + n \to n^2$ (leaves $n^{\log_2 4}$ dominate).
{exercise:uni-cs1001-master}
Practice
T(n) = 4T(n/2) + n solves to —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Leaves dominate: n^(log_2 4) = n^2.
Prove it by substitution
- Guess $T(n) \le c\,n\log n$ for $2T(n/2) + n$: substitute and the induction closes whenever $c \ge 1$ — the guess becomes a proof.
- Then measure: merge sort on the fixed 64-element course array makes $310$ comparisons, under the worst-case ceiling $n\log_2 n - n + 1 = 321$. Theory bounds, measurement confirms.
{exercise:uni-cs1001-substitute}
Practice
Merge sort on the 64-element course array makes — comparisons
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Measured 310, under the worst-case ceiling 321 = 64x6 - 64 + 1.