4.2 Recurrence Relations: Expansion, Summation, and Characteristic Equations

Ah Hua logs the cost of each layer in a recursive program, and now she wants to convert those layered dependencies into solvable recurrence relations.

Recursive algorithms break down large problems into smaller ones, and as a result, their runtime cost is defined by the cost of smaller subproblems. When translating code into a recurrence relation, the most important thing isn't memorizing formulas; it's counting how many subproblems are generated, their sizes, and the work performed at each current layer.

Sequence Recursion and Cost Recursion

A sequence recursion defines values:

Fₙ = Fₙ₋₁ + Fₙ₋₂

An algorithm's cost recursion describes runtime resources:

T(n) = T(n-1) + Θ(1)

Both use the same mathematical tools, but do not conflate function return value recursion with time recursion. An iterative algorithm computing Fibonacci numbers may still satisfy the Fibonacci recurrence relation, yet its time complexity is Θ(n).

From Code to Recurrence

long sum(long[] a, int n) {
    if (n == 0) return 0;
    return sum(a, n - 1) + a[n - 1];
}

If array access and addition are considered constant time:

T(0) = Θ(1)
T(n) = T(n-1) + Θ(1)

Expanding:

T(n) = T(n-1) + c
    = T(n-2) + 2c
    = ...
    = T(0) + nc
    = Θ(n)

The base cost does not determine asymptotic complexity, but it is part of the precise recurrence definition.

Expand and Telescope Summation

Recurrence:

T(n) = T(n-1) + n,  T(0) = c

Expansion:

T(n) = c + 1 + 2 + ... + n
    = c + n(n+1)/2
    = Θ(n²)

More generally:

T(n) - T(n-1) = g(n)

Summing from 1 to n, with intermediate terms canceling:

T(n) - T(0) = Σ_{i=1..n} g(i)

The problem thus reduces to estimating the sum.

Common asymptotic scales:

Σ 1 = Θ(n)
Σ i = Θ(n²)
Σ i² = Θ(n³)
Σ 1/i = Θ(log n)

Substitution is not "guessing the answer by expanding a few layers"

Substitution typically follows two steps:

1. Guess a bound by expanding the recurrence, examining the recursion tree, or drawing on experience;
2. Prove that bound using mathematical induction.

Example:

T(n) = T(⌊n/2⌋) + 1

Guess T(n)=O(log n). To prove it, find constants c,n₀ such that:

T(n) ≤ c log₂ n + d

and handle the base case and floor operations. Asymptotic proofs must not simply state "dividing by two repeatedly, so obviously true."

Recursive Tree: Layer-by-Layer Cost Accumulation

Merge sort:

T(n) = 2T(n/2) + cn

Recursive tree:

Layer 0: 1 problem, each merge cost cn       -> cn
Layer 1: 2 problems of size n/2, total      -> cn
Layer 2: 4 problems of size n/4, total      -> cn
...
Total of log₂n layers

Total internal cost cn log₂n, total leaf cost Θ(n), therefore:

T(n) = Θ(n log n)

A recursive tree can also help identify cases where subproblems are unequal in size or where layer costs vary. However, visualizing such cases still requires translation into upper and lower bound arguments.

Linear Homogeneous Recurrence and Characteristic Equation

Sequence:

aₙ = 3aₙ₋₁ - 2aₙ₋₂

Try solving aₙ=rⁿ:

r² = 3r - 2
r² - 3r + 2 = 0
(r - 1)(r - 2) = 0

Two distinct roots 1,2 yield the general solution:

aₙ = A·1ⁿ + B·2ⁿ

Use initial conditions to solve for A,B. If roots are repeated, the solution includes n rⁿ; if a nonhomogeneous term is present, a particular solution must also be found.

This method works well for linear recurrences with constant coefficients, but is not applicable to arbitrary recursions.

Fibonacci's Growth Rate

Fibonacci's characteristic equation:

r² = r + 1

The roots are:

φ = (1 + √5) / 2
ψ = (1 - √5) / 2

The sequence has Binet's formula:

Fₙ = (φⁿ - ψⁿ) / √5

Due to |ψ|<1, Fₙ=Θ(φⁿ).

The call cost of a naive recursive function satisfies approximately:

C(n) = C(n-1) + C(n-2) + Θ(1)

Thus it is also Θ(φⁿ); the common O(2ⁿ) is merely a loose upper bound. With memoization, each n is computed only once, resulting in time complexity Θ(n) and cache space Θ(n); iteration reduces the additional state to a constant number.

Don't Forget the Call Stack and Numerical Costs

Counting only recursive calls may overlook:

• The cost of slicing and copying at each level;
• The fact that integer addition grows beyond constant time as the number of bits increases;
• Stack space consumed by recursion depth;
• The computation required to generate hash keys for caching;
• I/O operations, locking, and memory allocation.

The number of digits in the Fibonacci numbers grows linearly with n, meaning that in any arbitrary-precision integer model, even if the algorithm performs only n additions, the cost of bit operations cannot be treated as constant forever.

Completion Checklist

1. Expand T(n)=T(n-1)+2n;
2. Use a recursive tree to solve T(n)=3T(n/3)+n;
3. Solve aₙ=5aₙ₋₁-6aₙ₋₂ using the characteristic equation;
4. Write out the value recurrence and call cost recurrence for the naive Fibonacci implementation;
5. List the time complexity, cache space, and call stack space for the memoized version.

References

• MIT Mathematics for Computer Science