Recurrence Relations
A recurrence relation defines a function in terms of its value at smaller inputs. For algorithm analysis, recurrences model the runtime of recursive algorithms:
T(n) = a · T(n/b) + f(n)
Where:
- a = number of subproblems
- n/b = size of each subproblem
- f(n) = cost of dividing and combining
Solving Methods
| Method | Approach | Best For |
|---|---|---|
| Substitution | Guess the form, prove by induction | When pattern is obvious |
| Recursion Tree | Expand the recurrence into a tree and sum levels | Visualizing cost distribution |
| Master Theorem | Direct formula for recurrences of form T(n) = aT(n/b) + f(n) | Quick solution |
Master Theorem
For T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1:
Compare f(n) with n^log_b(a):
- Case 1: f(n) = O(n^log_b(a) - ε) → T(n) = Θ(n^log_b(a))
- Case 2: f(n) = Θ(n^log_b(a) · log^k n) → T(n) = Θ(n^log_b(a) · log^(k+1) n)
- Case 3: f(n) = Ω(n^log_b(a) + ε) and a·f(n/b) ≤ c·f(n) → T(n) = Θ(f(n))
Common Recurrences
| Recurrence | Algorithm | Complexity |
|---|---|---|
| T(n) = T(n-1) + O(1) | Linear recursion | O(n) |
| T(n) = 2T(n/2) + O(n) | Merge sort | O(n log n) |
| T(n) = T(n/2) + O(1) | Binary search | O(log n) |
| T(n) = 2T(n-1) + O(1) | Towers of Hanoi | O(2ⁿ) |
| T(n) = T(n-1) + T(n-2) + O(1) | Naive Fibonacci | O(2ⁿ) |