Recurrence Relations

Recurrence relations are a mathematical sequence describing how a recurring algorithm divides/decreases the work done. Conventionally, $T(n)$ is used to denote the work done for input size $n$.

There are 2 ways to solve general recurrence relations to obtain a closed-form formula:

Iteration §

Iteration involves by building the relation from the bottom-up, by substituting small values of n.

For example: $a_n=a_{n-1}+3,a_0=2$ $a_1=a_0+3=2+3=5$ $a_2=a_1+3=a_0+3+3=2+3+3=8$ $a_3=a_2+3=a_1+3+3=a_0+3+3+3=2+3\ast 3=11$ $\dots a_n=2+3\ast n$

Telescoping §

Telescoping involves rearranging the equation and cancelling out terms

For example:  $T_n=T_{n-1}+2,T_0=1$

$T_1-T_0=2$ $+\cancel{T_2}-\cancel{T_1}=2$ $+\cancel{T_3}-\cancel{T_2}=2$ $+\dots T_n-\cancel{T_{n-1}}=2$
$\to T_n-T_0=2n$ $\to T_n=1+2n$

In Computer Science §

Most recurrence relations that use Divide-and-Conquer as a design pattern can be solved with the Master Theorem.