Recursive Closed Forms

Recursion Tree

Recursion Tree and Examples

A Recursion Tree is a technique for calculating the amount of work expressed by a recurrence equation
Consider $T(n) = 2T(\frac{n}{3}) + 6n$

$T(0) = 5$
These values are just chosen for illustration.

Now calculate $T(27) = T(3^3)$:

The Root of the tree is $T(27)$:

Upper part: $T(27)$
Lower part: $6n=6\times 27 = 162$

Children of root:

How many children?
What's in each child?

Calculating $T(27)$:

Tree Properties

Consider $T(n) = 6n + 2T(\frac{n}{3}) $

Bottom level is level $\log_3 27$ = level 3
Number of levels: $ 1 + \log_3 27 = 1 + 3 = 4$

$1 = 3^0$

Sum of level 0: $2^0 \times (6\times 27) = 142$
Sum of level 1: $2^1 \times (6\times 9) = 108$
Sum of level 2: $2^2 \times (6\times 3) = 72$

Sum of bottom level: $2^{\log_3 27} * 6 = 2^3 \times 6 = 48$

Sum of all levels: $142 + 108 + 72 + 48 = 370$

Recursion Tree for $T(n) = aT(\frac{n}{b}) + f(n)$

$T(1) = d$, Find $T(n)$

$T(n)=$\begin{cases} d & \text{if }n=1\\ a\times T(n/b)+f(n) & \text{otherwise} \end{cases}, where $n$ is a power of $b$.

What is the closed form solution of T(n)?

Let $b^{k}=n$, so $\text{log}_{b}n=k$. Using a change of variable, we can re-write the recurrence equation as

$t(k)=$\begin{cases} d & \text{if }k=0\\ a\times t(k-1)+f(b^{k}) & \text{otherwise} \end{cases}

$t(1)=a\times t(0)+f(b)$
$t(2)=a\times t(1)+f(b^{2})=a^{2}\times t(0)+a^{1}\times f(b)+a^{0}\times f(b^{2})$
$t(3)=a\times t(2)+f(b^{3})=a^{3}\times t(0)+a^{2}\times f(b)+a^{1}\times f(b^{2})+a^{0}\times f(b^{3})$
$t(4)=a\times t(3)+f(b^{4})=a^{4}\times t(0)+a^{3}\times f(b)+a^{2}\times f(b^{2})+a^{1}\times f(b^{3})+a^{0}\times f(b^{4})$

---> So, in general $t(k)=a^{k}\times t(0)+\sum_{i=0}^{k-1}a^{i}f(b^{k-i})=a^{k}\times d+\sum_{i=0}^{k-1}a^{i}f(b^{k-i})$

Since $k=\text{log}_{b}n$, we have

$T(n)=d\times a^{\text{log}_{b}n}+\sum_{i=0}^{\text{log}_{b}n-1}a^{i}f(\frac{n}{b^{i}})$

We could then use mathematical induction to verify this formula.

An Application of the Formula

---> Consider the following recurrence, defined for $n$ which is a power of 4 (for the time of some algorithm.) $T(n)=\begin{cases} 3 & \text{if }n=1\\ 2T(n/4)+4n+1 & \text{otherwise} \end{cases}$ ---> This recurrence equation is equivalent to $t(k)=\begin{cases} 3 & \text{if }k=0\\ 2\times t(k-1)+4\times4^{k}+1 & \text{otherwise} \end{cases}$ ---> Using the formula that we derived above, we could obtain \begin{array}{ccc} T(n) & = & 3\times2^{\text{log}_{4}n}+\sum_{i=0}^{\text{log}_{4}n-1}2^{i}\times\left[4\times\frac{n}{4^{i}}+1\right]\\ & = & 3\times n^{\frac{1}{2}}+4n\times\sum_{i=0}^{\text{log}_{4}n-1}\frac{1}{2^{i}}+\sum_{i=0}^{\text{log}_{4}n-1}2^{i}\\ & = & 3\times n^{\frac{1}{2}}+4n\times\frac{1-\left(\frac{1}{2}\right)^{\text{log}_{4}n}}{1-\frac{1}{2}}+\frac{1-2^{\text{log}_{4}n}}{1-2}\\ & = & 3\times n^{\frac{1}{2}}+8n\times(1-\frac{1}{n^{\frac{1}{2}}})+n^{\frac{1}{2}}-1\\ & = & 8n-4n^{\frac{1}{2}}-1 \end{array}

Evaluating the Complexity of the Sum of the Tree Levels

Sum of all levels: $\displaystyle \sum_{i=0}^{\text{log}_b n - 1} a^i f(\frac{n}{b^i}) + \Theta(n^{log_b a}) $

For the base case of recursion, we simply using $\Theta(1)$ instead of $d$

When this formula is a polynomial in $n$, the degree of the polynomial matters:

Either $f(n)$ or accumulation of $T(n)$ can dominate or they can be the same order

$\Theta(f(n))$, if the sum of non-leaf levels dominates (Case 1)
$\Theta(n^{\text{log}_b a}\lg n )$, if neither term dominates (Case 2)
$\Theta(n^{\text{log}_b a})$, if sum of leaves dominates (Case 3)