Divide & Conquer Algorithms - 4 - Recurrence
Solving Recurrence for Fibonacci Numbers
Suppose $n$ is even:
\[\begin{aligned} T(n) &= \mathbf{T(n-1)} + T(n-2) + 1\\ &= \mathbf{(T(n-2)+T(n-3)+1)} + T(n-2) + 1\\ &> 2\times T(n-2)\\ &> 2\times (\mathbf{2\times T(n-4)}) = 2^2 \times T(n-4)\\ &> 2^2\times (2\times T(n-6)) = 2^3 \times T(n-6)\\ &> 2^3\times (2\times T(n-8)) = 2^4 \times T(n-2\times 4)\\ &\vdots\\ &>2^k \times \mathbf{T(n-2k)}\\ &\vdots\\ &> 2^{\mathbf{\frac n 2}}\times \mathbf{T(0)}\\ &= 2^{\frac n 2} \end{aligned}\]Suppose $n$ is odd:
\[\begin{aligned} T(n) &> 2^{\mathbf{\frac{n-1} 2}} \times \mathbf{T(1)}\\ &=2^{\frac{n-1} 2} \end{aligned}\]The expressions being operated on are in bold.
Solving Recurrence for Merge Sort
\(T(n)=\begin{cases} 1 & \text{if } n= 1\\ 2\times T(\frac n 2)+n & \text{if } n> 1 \end{cases}\)
Solving the Recurrence
\[\begin{aligned} T(n) &= 2\times \mathbf{T\left(\frac n 2\right)} +n\\ &=2\times(\mathbf{2\times T\left(\frac n{2^2}+\frac n 2\right)}+n=2^2\times T\left(\frac n{2^2}\right)+2n\\ &=2^2\times(2\times T\left(\frac n{2^3}+\frac n {2^2}\right)+2n=2^3\times T\left(\frac n{2^3}\right)+3n\\ &\vdots\\ &= 2^{\log n}\times T\left(\frac n{2^{\log n}}\right) + (\log n) \times n\\ &= 2^{\log n}\times T(1) +(\log n)\times n\\ &= n+n\log n\\ &= O(n\log n) \end{aligned}\]Summary
For the following recurrences, the following time complexities are true:
- $T(n)=2\times T\left(\frac n 2\right) +1$
- $T(n)$ is $O(n)$.
This is for finding sum/min/max.
- $T(n)=2\times T\left(\frac n 2\right) +n$
- $T(n)$ is $O(n\log n)$.
This is merge sort.
- $T(n)=2\times T(n-1) +1$
- $T(n)$ is $O(2^n)$.
This is Fibonacci numbers.
- $T(n)=T\left(\frac n 2\right) +1$
- $T(n)$ is $O(\log n)$.
This is for recursive binary search.