Recurrence Relations

So you need an infinite sequence? How are you going to give a finite description of it?

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)^2$
$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 - 2$
$C(0) = 1, C(n+1) = \sum\limits_{i=0}^n C(i)C(n-i)$

Exercise: Hone your math skills by working out the first 10 values of each of these sequences.

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));
}

Here $T(0) = 1$ and $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$, and $T(n) = 2T(\frac{n}{2}) + n$.

Mergesort uses the divide and conquer strategy. Specifically Mergesort breaks the input into $2$ pieces each of size $\frac{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 $\frac{n}{b}$, recurses on those pieces, then assembles a solution with $f(n)$ operations. Here is the theorem given without proof:

If $T(n) = c\;\mathrm{if}\;n=1\;\mathrm{else}\;aT(\frac{n}{b}) + f(n)$, where $f \in O(n^d)$, $a \ge 1$, $b \ge 2$, $c > 0$, and $d \geq 0$, then:

\[ T \in \left\{ \begin{array}{l l} O(n^d) & \textrm{ if } d > \log_b{a} \\ O(n^d \log n) & \textrm{ if } d = \log_b{a} \\ O(n^{\log_b{a}}) & \textrm{ if } d < \log_b{a} \end{array} \right. \]

Examples:

$T(n) = 2T(n/2) + n^2 \Rightarrow a=2, b=2, d=2, 2 > \log_2 2 ⇒ T \in O(n^2)$
$T(n) = 2T(n/2) + n \Rightarrow a=2, b=2, d=1, 1 = \log_2 2 \Rightarrow T \in O(n \log n)$
$T(n) = 5T(n/3) + n^{0.5} \Rightarrow a=5, b=3, d=0.5, 0.5 < \log_3 5 \Rightarrow T \in O(n^{\log_3 5})$