39 Two methods to solve recurrences

Method 1: Unrolling the recurrence

• “Opening up” the recurrences step-by-step
• Doesn’t need any idea about the final answer!

Revisiting the recurrence of MergeSort

Unrolling the recurrence $T(n)\le 2\cdot T(n/2)+O(n)$.
We first write this recurrence explicitly as follows: for some constant $c$

• $T(n)\le 2\cdot T(n/2)+cn$ for each $n>2$ $\to$ for some constant $c$ (by definition of big $O$)
• Best Case: $T(2)\le c$

Three steps to solve this recurrence:

• Analyse the first few levels $\to$ level 0, level 1, level 2, $\cdots$
• Identify a pattern $\to$ seems to be doing $(cn)$ work at each level
• Sum up over all levels of recursion $\to$ If I have $r$ levels, then $\frac{n}{2^r}=$ Size of base case = 2 $=n=2^{r+1}\approx r={\log }_n-1$. So total work is $T(n)=cn\cdot \log n$

Another example

Merge Sort $=T(n)\le 2\cdot T(n/2)+O(n)$.
New Example = $=T(n)\le a\cdot T(n/b)+O(n)$ $a,b$ are constants

Level below it

At level $r$, I have $a^r$ instances each having size $\frac{n}{b^r}$.
Base Case $=T(b)=c$

• How many Levels?
  • If I have $r$ levels, then $\frac{n}{b^r}=$ size at level $r$ = size of base case = $b$
  • $n=b^{r+1}\Rightarrow r+1={\log }_{b}n\Rightarrow r=({\log }_{b}n)-1$

At level $i$, we do $c\cdot \frac{n}{b^i}\times a^i$.
Total levels $=({\log }_{b}n)-1$.
Total work done

$$\begin{array}{rl}T(n)& \le \sum _{i=0}^{({\log }_{b}n)-1}cn\cdot \frac{a^i}{b^i}\\ T(n)& \le cn\sum _{i=0}^{({\log }_{b}n)-1}(\frac{a}{b}{)}^i\\ T(n)& =\{\begin{array}{ll}\Theta (n)& a<b\\ \Theta (n\log n)& a=b\\ \Theta (n^{{\log }_{b}a})& a>b\end{array}\end{array}$$

Method 2: Verifying by substitution in the recurrence

• Works if you already have a guess for the running time!
• Check (by induction) whether your guess is satisfied by the recurrence.

We first write this recurrence explicitly as follows: for some constant $c$

• $T(n)\le 2\cdot T(n/2)+cn$ for each $n>2$ $\to$ for some constant $c$ (by definition of big $O$)
• Best Case: $T(2)\le c$

Suppose we believe that $T(n)\le cn\cdot {\log }_{2}n$ is true, and we want to verify it!

Proof by induction using susbtitution

• Base case is $n=2$
  • $T(2)\le c\le cn\cdot {\log }_{2}n$
• Inductive Hypothesis
  • For each $2\le m<n$ we have $T(m)\le cm\cdot logm$
• Inductive Step:

$$\begin{array}{rl}T(n)& =2T(n/2)+cn\text{by the recurrence}\\ & \le 2c\cdot (n/2)\cdot \log (n/2)+cn\text{by inductive hypothesis since }n/2<n\\ & =cn(\log n-1)+cn\text{since }\log (n/2)=\log n-1\\ & =cn\cdot \log n\end{array}$$

Note

By this method, we have verified that $T(n)=cn\cdot \log n$ is one possible solution for this recurrence. Unlike the previous method of unrolling, this might lead to just verifying that a much higher running time is correct!