Recurrence Analysis

Recurrence

A recurrence is an equation/inequality according to which the $n$th term of a sequence of numbers is equal to some combination of the previous terms.

There are roughly three methods to solve recurrences:

1. Substitution Method: Guessing the closed form using substitution and then prove by induction.
2. Recursion Tree: Guessing the closed form using the recurrence tree and then prove by induction.
3. Master Theorem: Finding asymptotic bounds of some recurrences using predefined rules.

We will now introduce the last two methods.

Recursion Tree

Recursion Tree

Recursion tree is a tree where:

• Each node represents a single sub-problem along with the cost of the particular sub-problem.
• An edge from node $v$ to node $u$ means that the sub-problem represented by node $v$ calls the sub-problem represented by node $u$.
  

e.g. For the recurrence $T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+cn$ where $c$ is a constant and $T(1)=1$:

Note that not all leaves are in the last level, hence the total cost is at most $\#\text{levels}\times cn=cn({\log }_{\frac{3}{2}}n+1)\in O(n\log n).$

Master Theorem

Master Theorem

Consider $T(n)=aT(\frac{n}{b})+f(n),a\ge 1,b>1$, $\frac{n}{b}$ can be $\lceil \frac{n}{b}\rceil$ or $\lfloor \frac{n}{b}\rfloor$.

1. If $f(n)=O(n^{({\log }_{b}a)-ϵ})$ for some constant $ϵ>0$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
2. If $f(n)=\Theta (n^{{\log }_{b}a})$, then $T(n)=\Theta (n^{{\log }_{b}a}\log n)$. More generally, if $f(n)=\Theta (n^{{\log }_{b}a}(\log n{)}^k)$ for some integer $k\ge 0$, then $T(n)=\Theta (n^{{\log }_{b}a}(\log n{)}^{k+1})$.
3. If $f(n)=\Omega (n^{({\log }_{b}a)+ϵ})$ for some constant $ϵ>0$ and if $af(\frac{n}{b})\le cf(n)$ for some constant $c<1$ and $n>n_0$, then $T(n)=\Theta (f(n))$.
   

e.g. Consider $T(n)=2T\left(\frac{n}{2}\right)+n$. Here $a=2$, $b=2$, $f(n)=n$. Hence $n^{{\log }_{b}a}=n$. Therefore by second case of Master theorem we have $T(n)=\Theta (n\log n)$.