Iterative Method for Recursive Complexities

Method §

This method works by expanding the recurrence to obtain a summation, and subsequently evaluation this summation to obtain a solution.

Examples §

Simple example §

Given a recurrence relation

$$T(n)=\{\begin{array}{rlr}& 0& n=0\\ & c+T(n-1)& n>0\end{array}$$

We can iteratively expand $T(n)$ as

• $c+T(n-1)$
• $c+c+T(n-2)$
• $c+c+c+T(n-3)$ A pattern can easily be recognised here and this can be generalised to $T(n)=kc+T(n-k)$ for $k<n$. When $k=n$, $T(n)=nc+T(0)=nc$. As such, $T(n)=O(n)$.

More complex example §

The previous example was unrealistically simple. Different methods are required for more complex recurrences, such as:

$$T(n)=\{\begin{array}{rlr}& c& n=1\\ & 2T(\frac{n}{2})+c& n>1\end{array}$$

The first few expansions are:

• $2T(\frac{n}{2})+c$
• $2^{2}T(\frac{n}{2^2})+2c+c$
• $2^{3}T(\frac{n}{2^3})+3c+c$ The general formula for $k<n$ can easily be identified as $2^{k}T(\frac{n}{2^k})+(2^k-1)c$ To obtain the base case $T(1)$, we select $k=\log n$, giving

$$T(n)=2^{\log n}T(\frac{n}{\log n})+(2^{\log n}-1)c$$

We can use the mathematical fact $a^{{\log }_{b}c}=c^{{\log }_{b}a}$ to obtain

$$\begin{array}{rl}T(n)& =nT(\frac{n}{n})+(n-1)c\\ & =nc+(n-1)c\\ & =(2n-1)c\\ & =O(n)\end{array}$$

Master method example §

Applying this method to the recurrence

$$T(n)=\{\begin{array}{rlr}& c& n=1\\ & aT(\frac{n}{b})+cn& n>1\end{array}$$

can reveal much of the reasoning behind the Master Method for Recursive Complexities.