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$.

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

Formula §

If $T(n)=\{\begin{array}{ll}aT(\frac{n}{b})+n^k,& n>1\\ d,& n=1\end{array}$ where

• $a$ = The amount of subproblems that are used by the algorithm.
• $b$ = The factor by which the n problem is divided into.
• $k$ = The polynomial factor of n, the additional work done by the algorithm then:

$T(n)=\{\begin{array}{ll}O(n^k),& a<b^k\\ O(n^{k}log(n)),& a=b^k\\ O(n^{{\log }_{b}a}),& a>b^k\end{array}$

For example, take the example of a divide-and-conquer algorithm, mergesort. The recursion tree of mergesort is as follows:

Link to source

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

• Iteration
• Telescoping

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$