Recurrence Analysis

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

Fact Three Methods for Recurrence Analysis

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.

Def 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 𝑣 to node 𝑢 means that the sub-problem represented by node 𝑣 calls the sub-problem represented by node 𝑢.

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 total cost is at most $\#levels\times cn=cn({\log }_{\frac{3}{2}}n+1)\in O(n\log n)$.

Master Theorem

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