Divide and Conquer Unrolling Examples

Unrolling is a method for time complexity analysis for divide and conquer problems. The method is introduced in Unrolling.

Example 1

Given the sample recurrence relation:

1. Start with the given recurrence relation $T(n)=T(n-1)+n$
2. Substitute the relation iteratively(the size of the subproblem is reduced by 1 each time in this example) $T(n)=T(n-1)+n$ First iteration $T(n-1)$:

$$\begin{array}{rl}T(n-1)& =T((n-1)-1)+(n-1)\\ & =T(n-2)+(n-1)\end{array}$$

Substitute the $T(n-1)$ back to the original equation.

$$\begin{array}{rl}T(n)& =T(n-1)+n\\ & =(T(n-2)+(n-1))+n\\ & =T(n-2)+(n-1)+n\end{array}$$

Second iteration $T(n-2)$:

$$\begin{array}{rl}T(n-2)& =T((n-2)-1)+(n-2)\\ & =T(n-3)+(n-2)\end{array}$$

Substitute the $T(n-2)$ back to the original equation.

$$\begin{array}{rl}T(n)& =T(n-2)+(n-1)+n\\ & =(T(n-3)+(n-2))+(n-1)+n\\ & =T(n-3)+(n-2)+(n-1)+n\end{array}$$

3. Identify the pattern $T(n)=T(n-3)+(n-2)+(n-1)+n$ $T(n)=T(n-k)+(n-k+1)+(n-k+2)+\dots +n$ When $k=n$, we reaches the base case $T(0)$. $T(n)=T(0)+1+2+3+\dots +n$ Assuming $T(0)=0$:

$$\begin{array}{rl}T(n)& =0+1+2+3+\dots +n\\ & =1+2+3+\dots +n\end{array}$$

We can conclude that the pattern fits the arithmetic series. 4. Summing the terms We can sum up the terms using the arithmetic series rules. $T(n)=\frac{n(1+n)}{2}$ 5. Finalise the solution Evaluate the time complexity:

$$\begin{array}{rl}T(n)& =\frac{n(1+n)}{2}\\ & =\frac{n+n^2}{2}\\ & =\frac{n}{2}+\frac{n^2}{2}\\ & =\frac{n^2}{2}\\ & =n^2\end{array}$$

Now, we can conclude the asymptotic complexity to be: $T(n)=\text{Uptheta}(n^2)$

Example 2

1. Start with the given recurrence relation $T(n)=T(\frac{n}{2})+O(n)$
2. Substitute the relation iteratively(the size of the subproblem is halved each time) First iteration $T(\frac{n}{2})$:

$$\begin{array}{rl}T(\frac{n}{2})& =T(\frac{\frac{n}{2}}{2})+(\frac{n}{2})\\ & =T(\frac{n}{4})+(\frac{n}{2})\end{array}$$

Substitute the $T(\frac{n}{2})$ back to the original equation:

$$\begin{array}{rl}T(n)& =T(\frac{n}{2})+n\\ & =(T(\frac{n}{4})+(\frac{n}{2}))+n\\ & =T(\frac{n}{4})+(\frac{n}{2})+n\end{array}$$

Second iteration $T(\frac{n}{4})$:

$$\begin{array}{rl}T(\frac{n}{4})& =T(\frac{\frac{n}{4}}{2})+(\frac{n}{4})\\ & =T(\frac{n}{8})+(\frac{n}{4})\end{array}$$

Substitute the $T(\frac{n}{4})$ back to the original equation:

$$\begin{array}{rl}T(n)& =T(\frac{n}{2})+n\\ & =(T(\frac{n}{4})+(\frac{n}{2}))+n\\ & =(T(\frac{n}{8})+(\frac{n}{4}))+(\frac{n}{2})+n\end{array}$$

3. Identify the pattern

$$\begin{array}{rl}T(n)& =T(n\times \frac{1}{8})+(n\times \frac{1}{4})+(n\times \frac{1}{2})+n\\ & =T(n\times \frac{1}{k})+(n\times \frac{1}{\frac{k}{2}})+(n\times \frac{1}{\frac{k}{4}})+\cdots +n\end{array}$$

When $k=n$, we reaches the base case $T(1)$:

$$\begin{array}{rl}T(n)& =T(1)+(n\times \frac{1}{\frac{n}{2}})+(n\times \frac{1}{\frac{n}{4}})+\cdots +n\\ & =T(1)+2+4+\cdots +n\end{array}$$

Assumes $T(1)=1$ $T(n)=1+2+4+\cdots +n$ The geometric series has the form: $a+ar+a{r}^2+a{r}^3+\cdots +a{r}^{k-1}$ We can discover the first term $a=1$ common ratio $r=2$, the number of terms is $k$

4. Summing the terms Apply the geometric series:

$$T(n)=1+2+4+\cdots +2^{k-1}$$

We known that the last term is $n$, therefore $2^{k-1}=n$ Solve for $k$:

$$\begin{array}{rl}{2}^{k-1}& =n\\ k-1& ={\log }_{2}n\\ k& ={\log }_{2}n+1\end{array}$$

Thus, the number of terms $k={\log }_{2}n+1$ We apply the sum of geometric series formula: $S_n=\frac{a(r^k-1)}{r-1}$

$$\begin{array}{rl}T(n)& =\frac{1(2^{{\log }_{2}n+1}-1)}{2-1}\\ & =2^{{\log }_{2}n+1}-1\\ & =(2^{{\log }_{2}n}\times 2)-1\\ & =n\times 2-1\\ & =2n-1\end{array}$$

5. Evaluate the time complexity

$$\begin{array}{rl}T(n)& =2n-1\\ & =n\end{array}$$

Therefore, the time complexity of the given recurrence relation is linear, denoted as $\text{Uptheta}(n)$

---

Back to parent page: Divide and Conquer

AlgorithmDivide_and_ConquerUnrolling