Recurrences

Overview

A recurrence is an equation that describes a function in terms of its value on other, typically smaller, arguments. A recurrence $T (n)$ is algorithmic if, for every sufficiently large threshold constant $n_{0} > 0$ , the following two properties hold:

For all $n < n_{0}$ , we have $T (n) = Θ (1)$ .
For all $n \geq n_{0}$ , every path of recursion terminates in a defined base case.

Finding Bounds

Substitution

In the substitution method, one guesses the form of a bound and then uses mathematical induction to prove the guess correct and solve for constants. In general, there are two steps:

Guess the form of the solution using symbolic constants.
Use mathematical induction to show the solution works and find the constants.

Recursion-Tree

In the recursion-tree method, one models the recurrence as a tree whose nodes represent the costs incurred at various levels of the recursion. To then solve the recurrence, one determines the costs at each level and adds them up.

Generally speaking, once a reasonable guess has been derived, the substitution method is then used to formally prove the result.

Master Theorem

Let $a > 0$ and $b > 1$ be constants. Recurrences of form $T (n) = a T (n / b) + f (n)$ are called master recurrences. The $f (n)$ term is called the driving function.

Let $a > 0$ and $b > 1$ be constants, and let $f (n)$ be a driving function that is defined and nonnegative on all sufficiently large reals. Define the recurrence $T (n)$ on $n \in N$ by

T (n) = a T (n / b) + f (n),

where $a T (n / b)$ actually means $a_{1} T (⌊ n / b ⌋) + a_{2} T (⌈ n / b ⌉)$ for some constants $a_{1} \geq 0$ and $a_{2} \geq 0$ satisfying $a = a_{1} + a_{2}$ . Then the asymptotic behavior of $T (n)$ can be characterized as follows:

If there exists a constant $ϵ > 0$ such that $f (n) = O (n^{\log_{b} a - ϵ})$ , then $T (n) = Θ (n^{\log_{b} a})$ .
If there exists a constant $k \geq 0$ such that $f (n) = Θ (n^{\log_{b} a} \lg^{k} n)$ , then $T (n) = Θ (n^{\log_{b} a} \lg^{k + 1} n)$ .
If there exists a constant $ϵ > 0$ such that $f (n) = Ω (n^{\log_{b} a + ϵ})$ , and if $f (n)$ additionally saitisfies the regularity condition $a f (n / b) \leq c f (n)$ for some constant $c < 1$ and all sufficiently large $n$ , then $T (n) = Θ (f (n))$ .

Solving Recurrences

To solve a recurrence relation means to find a closed form for the relation (with respect to initial conditions).

Telescoping

We can use telescoping to solve recurrences of form $a_{n} = a_{n - 1} + f (n)$ by noticing that:

\begin{aligned} a_{1} - a_{0} & = f (1) \\ a_{2} - a_{1} & = f (2) \\ ⋮ \\ a_{n} - a_{n - 1} & = f (n) \\ a_{n} - a_{0} & = \sum_{k = 1}^{n} f (n) \end{aligned}

Iteration

Iteration refers to the expansion of terms, starting at the initial conditions, in the hope of discovering a pattern. It is more general than telescoping is.

A recurrence of form $a_{n} = a_{n - 1} + f (n)$ can be solved with iteration like so:

\begin{aligned} a_{1} & = a_{0} + f (1) \\ a_{2} & = (a_{0} + f (1)) + f (2) \\ ⋮ \\ a_{n} & = (\dots (a_{0} + f (1)) + f (2)) + \dots) + f (n) \\ a_{n} & = a_{0} + \sum_{k = 1}^{n} f (n) \end{aligned}

Characteristic Roots

When encountering linear homogeneous recurrence relations with constant coefficients, we can use the characteristic root technique to solve. We demonstrate with a quadratic characteristic polynomial, though this technique generalizes to higher-order polynomials as well.

Given recurrence relation $a_{n} + α a_{n - 1} + β a_{n - 2} = 0$ , the characteristic polynomial is $r^{2} + α r + β$ . If $r_{1}$ and $r_{2}$ are distinct roots of the characteristic polynomial, then the solution to the recurrence relation is

a_{n} = a r_{1}^{n} + b r_{2}^{n}

where $a$ and $b$ are determined by the initial conditions. If the characteristic polynomial only has one root $r$ , the solution is instead

a_{n} = a r^{n} + b n r^{n} .