4.2 Recurrence Relations: Expansion, Summation, and Characteristic Equations

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.

Value Recurrences and Cost Recurrences

A value recurrence defines values:

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

An algorithm's cost recurrence 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 it takes Θ(n) time when each addition has unit cost.

From Code to Recurrence

This Java method assumes a!=null, 0≤n≤a.length, no mutation while reading, and prefix sums that fit long. It illustrates recursive cost; a large n may exhaust the call stack first.

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)

Using the same positive constant c at every step makes the expansion exact. The original Θ(1) only requires uniform positive constant bounds, which also yield linear total cost. A fixed positive base cost does not change this example’s asymptotic order, but remains part of its recurrence definition.

Expansion and Telescoping Sums

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.

With every sum indexed by i=1,...,n:

Σ 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."

Set T(1)=d and apply the recurrence for integer n≥2. The exact solution is T(n)=d+⌊log₂n⌋: for n≥2, ⌊log₂⌊n/2⌋⌋=⌊log₂n⌋−1, so substitution of the induction hypothesis restores the formula; n=1 satisfies the base case. This Python 3 counter uses integer division, avoiding floating-point log rounding:

def halvings(n):
    if n < 1:
        raise ValueError("positive integer required")
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

print([halvings(n) for n in [1, 2, 3, 4, 7, 8]])  # [0, 1, 1, 2, 2, 3]

Recursion Tree: Adding Costs by Level

First take n=2^k and T(1)=Θ(1) for 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
...
log₂n internal levels, plus one leaf level

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

T(n) = Θ(n log n)

A recursion 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.

For a₀=2,a₁=3, the equations A+B=2,A+2B=3 give A=B=1, hence aₙ=1+2ⁿ. Generate the recurrence independently and compare it with the closed form:

values = [2, 3]
for n in range(2, 9):
    values.append(3 * values[-1] - 2 * values[-2])
assert values == [1 + 2**n for n in range(9)]
print(values[:5])  # [2, 3, 5, 9, 17]

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 formula is exact over the real numbers. Computing floating-point φⁿ and rounding is not a reliable integer algorithm for arbitrarily large n, because exponentiation amplifies rounding error.

The call cost of a naive recursive function satisfies approximately:

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

Under unit-cost arithmetic, the naive algorithm takes Θ(φⁿ) time; O(2ⁿ) is a looser upper bound. Counting calls gives C(0)=C(1)=1 and C(n)=C(n-1)+C(n-2)+1, hence C(n)=2Fₙ₊₁−1 by induction. This small example accepts a nonnegative integer and returns the value and call count:

def fib_with_calls(n):
    if n < 2:
        return n, 1
    a, ca = fib_with_calls(n - 1)
    b, cb = fib_with_calls(n - 2)
    return a + b, 1 + ca + cb

print(fib_with_calls(10))  # (55, 177)

Memoization expands each index once, using Θ(n) arithmetic operations and cache entries; recursive stack depth remains Θ(n). Iteration needs a constant number of big-integer variables, which does not mean a constant number of storage bits.

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.

With linear-bit-cost big-integer addition, iteration takes Θ(1+2+...+n)=Θ(n²) total addition work and Θ(n) bits for working integers. Caching all first n terms stores Θ(n²) numeric bits. These are bit-model bounds, excluding runtime costs such as object headers.

Completion Checklist

1. Expand T(n)=T(n-1)+2n;
2. Use a recursion 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