Recurrence Relations

Definition

A recurrence relation is a recursive definition of a sequence.

Examples

• F(0) = 0, F(1) = 1, F(n+2) = F(n) + F(n+1)
• P(0) = 0.01, P(n+1) = 4P(n) − 3P(n)²
• T(0) = 1, T(n+1) = T(n) + 1
• S(0) = 0, S(n+1) = S(n) + 2n + 1
• A(0) = 4, A(n+1) = A(n)² − 2
• C(0) = 1, C(n+1) = Σⁿ_i=0C(i)C(n−i)

Uses

These things show up all the time when doing complexity analysis of recursive functions.

Example — Sum of list elements

function sum(a) {
    return a == [] ? 0 : head(a) + sum(tail(a));
}

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

Example — Mergesort

function sort(a) {
    if length(a) <= 1 {
        return a;
    } else {
        mid = length(a) / 2;
        return merge(sort(a[0..mid-1]), sort(a[mid..length(a)-1]));
    }
}

T(0) = 1, T(1) = 1, T(n) = 2T(n/2) + n

Mergesort uses the divide and conquer strategy. Specifically Mergesort breaks the input into 2 pieces each of size n/2, recurses on those pieces, then assembles a solution with n operations. How do we compute the complexity of this?

The Master Theorem

The Master Theorem tells us how to find a "closed form" complexity function for algorithms that break the input into a pieces each of size n/b, recurses on those pieces, then assembles a solution with f(n) operations. Here is the theorem given without proof:

If T(n) = aT(⌈n/b⌉) + f(n) and f(n) ∈ O(n^d) and a ≥ 0, b > 1, d > 0, then T(n) ∈

• O(n^d)             if d > log_ba
• O(n^d log n)    if d = log_ba
• O(n^log_ba)       if d < log_ba

Examples

• T(n) = 2T(n/2) + n² ⇒ a=2, b=2, d=2, 2 > log₂2 ⇒ O(n²)
• T(n) = 2T(n/2) + n ⇒ a=2, b=2, d=1, 1 = log₂2 ⇒ O(n log n)
• T(n) = 5T(n/3) + n^0.5 ⇒ a=5, b=3, d=0.5, 0.5 < log₃5 ⇒ O(n^log₃5)