Recurrence Relations
Definitions
Formulas
Solving Linear Homogeneous Recurrences
Step-by-Step Method
- Write the characteristic equation from the recurrence
- Solve the characteristic equation for roots
- If roots are distinct:
- If a root has multiplicity : include terms
- Use initial conditions to solve for constants
Example: Fibonacci Sequence
The Fibonacci recurrence with :
Characteristic equation:
Roots: ,
General solution:
Using initial conditions: ,
Closed form:
Python Implementations
Solving Linear Recurrences
import numpy as np
from functools import lru_cache
def solve_linear_recurrence(c1, c2, a0, a1, n):
"""Solve a_n = c1*a_{n-1} + c2*a_{n-2}."""
coeffs = [1, -c1, -c2]
roots = np.roots(coeffs)
if len(set(np.round(roots, 10))) == 2:
r1, r2 = roots
A = (a1 - r2 * a0) / (r1 - r2)
B = a0 - A
return A * r1**n + B * r2**n
else:
r = roots[0]
return (a0 + n * (a1 / r - a0)) * r**n
# Fibonacci
for i in range(11):
print(f"F({i}) = {solve_linear_recurrence(1, 1, 0, 1, i):.0f}")
Iterative Solution
def linear_recurrence_iterative(c1, c2, a0, a1, n):
"""Compute a_n iteratively."""
if n == 0:
return a0
if n == 1:
return a1
prev2, prev1 = a0, a1
for _ in range(2, n + 1):
curr = c1 * prev1 + c2 * prev2
prev2, prev1 = prev1, curr
return prev1
# Verify
for n in range(11):
print(f"F({n}) = {linear_recurrence_iterative(1, 1, 0, 1, n)}")
Memoized Recursion
@lru_cache(maxsize=None)
def fibonacci_memo(n):
if n <= 1:
return n
return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
for i in range(20):
print(f"F({i}) = {fibonacci_memo(i)}", end=" ")
Master Theorem
Master Theorem Applications
| Algorithm | Recurrence | Complexity | |||
|---|---|---|---|---|---|
| Binary Search | 1 | 2 | 0 | ||
| Merge Sort | 2 | 2 | 1 | ||
| Strassen | 7 | 2 | 2 | ||
| Karatsuba | 3 | 2 | 1 |
import math
def master_theorem(a, b, d):
log_b_a = math.log(a) / math.log(b)
if d < log_b_a:
return f"O(n^{log_b_a:.2f})"
elif abs(d - log_b_a) < 1e-9:
return f"O(n^{d} log n)"
else:
return f"O(n^{d})"
print(master_theorem(2, 2, 1)) # O(n^1.00 log n) - Merge Sort
print(master_theorem(1, 2, 0)) # O(n^0.00 log n) = O(log n) - Binary Search
print(master_theorem(7, 2, 2)) # O(n^2.81) - Strassen
Non-Homogeneous Recurrences
Applications in AI/ML
Common Mistakes
| Mistake | Correction |
|---|---|
| Forgetting initial conditions | The general solution has undetermined constants; use to solve them |
| Applying Master theorem to non-divide-and-conquer | Master theorem requires form exactly |
| Mixing up cases in Master theorem | Compare with , not with or individually |
| Ignoring repeated roots | Repeated roots require polynomial factors: not just |
| Assuming closed form always exists | Not all recurrences have nice closed forms |
| Using Master theorem on | This is not divide-and-conquer; solve by iteration or substitution |
| Forgetting to verify solution against base cases | Always check that your closed form produces the correct initial values |
| Confusing homogeneous and non-homogeneous | Non-homogeneous has an extra term; treat separately |
Interview Questions
-
What is the Master theorem and when does it apply? It solves in three cases based on comparing with . It applies only to divide-and-conquer recurrences.
-
How do you solve the Fibonacci recurrence? Characteristic equation gives roots and . Closed form: .
-
What is the time complexity of merge sort and why? . The recurrence satisfies Case 2 of Master theorem with .
-
How do you solve a recurrence with repeated roots? If root has multiplicity 2, the solution is instead of just .
-
What is the difference between linear and non-linear recurrences? Linear recurrences express as a linear combination of previous terms. Non-linear recurrences involve products, powers, or other non-linear functions of previous terms.
-
How do you analyze recursive algorithms without Master theorem? Use the recursion tree method: sum work at each level, or use substitution method (guess and verify by induction).
-
What is the Akra-Bazzi method? Generalizes Master theorem for recurrences like where can be any polynomial.
-
When does the Master theorem not apply? When the recurrence is not divide-and-conquer (e.g., ), or when subproblems have unequal sizes.
Practice Problems
Recursion Tree Method
def recursion_tree_depth(T_func, n, depth=0):
"""Visualize recursion tree depth."""
if n <= 1:
return depth
return T_func(n, depth)
def sum_of_geometric_series(a, r, n):
"""Sum of geometric series: a + ar + ar^2 + ... + ar^(n-1)."""
if abs(r) < 1:
return a * (1 - r**n) / (1 - r)
return a * (r**n - 1) / (r - 1)
# Example: T(n) = 2T(n/2) + n has log2(n) levels, each doing n work
import math
for n in [8, 16, 32, 64]:
levels = int(math.log2(n))
total = sum(n // (2**i) * 2**i for i in range(levels + 1))
print(f"T({n}): {levels} levels, total work ~ {total}, O(n log n) = {n * levels}")
Substitution Method
def substitution_verify(c1, c2, bound_func, n_values):
"""Verify a guessed bound satisfies the recurrence."""
for n in n_values:
if n <= 1:
continue
lhs = c1 * bound_func(n)
rhs = c2 * bound_func(n // 2) + n
if lhs < rhs:
return False, n
return True, None
import math
result, failing_n = substitution_verify(1, 2, lambda n: n * math.log2(n), [4, 8, 16, 32])
print(f"Bound O(n log n) verified: {result}")
Quick Reference
| Recurrence | Solution | Complexity | Method |
|---|---|---|---|
| Iteration | |||
| Iteration | |||
| Iteration | |||
| Master Case 2 | |||
| Master Case 2 | |||
| Master Case 1 | |||
| Master Case 1 | |||
| Characteristic | |||
| Varies | Characteristic |
Cross-References
- Graph Theory β Discrete Graphs: BFS/DFS traversals have recursive definitions
- Trees β Discrete Trees: Tree height and operations satisfy recurrences
- Number Theory β Discrete Number Theory: Modular exponentiation uses recurrences
- Boolean Algebra β Discrete Boolean: Boolean function complexity
- Automata Theory β Discrete Automata: Grammar production rules are recursive
- Applications β Discrete Applications: Algorithm analysis uses recurrences extensively