Divide & Conquer Running Time
Running Time of Divide & Conquer
We can use a recurrence relation to analyse the running time where:
- $T(n)$ denotes the running time on an input of size $n$.
We can then extend this with a case statement that relates $T(n)$ to values of the function $T$ for problem sizes smaller than $n$.
For example, the running time of merge sort can be written in this form:
\[T(n) = \begin{cases} c & \text{if }n<2\\ 2T(\frac n 2)+cn &\text{otherwise} \end{cases}\]$c$ is a small constant that represents how much work is done for the each iteration.
Substitution Method
One way to solve a divide and conquer recurrence equation is to use the iterative substitution method. For the previous example
\[T(n) = \begin{cases} c & \text{if }n<2\\ 2T(\frac n 2)+cn &\text{otherwise} \end{cases}\]Assuming that $n$ is a power of 2 we get:
\[\begin{aligned} T(n) &= 2\left(2T(\frac n {2^2}) +c(\frac n 2)\right)+cn\\ &=2^2 T(\frac n {2^2}) + 2cn \end{aligned}\]For $i=\log_2n$, we get:
\[\begin{aligned} T(n) &= 2^{\log_2n}\times c + cn\log_2n\\ &=cn + cn \log_2n\\ &= \Theta(n\log n) \end{aligned}\]General Method
We can also use this method which may be simpler: Divide & Conquer Tutorial - Running Time Alternate Method
We can use a more general method that takes the form:
\[T(n)= \begin{cases} c & \text{if } n\leq d\\ aT(\frac n b)+f(n) & \text{if } n>d \end{cases}\]with some constants $a,b,c$ and $d$, and some function $f(n)$.
$f(n)$ accounts for the recursive preparation time and the time taken to merge.
We can “unwind” this recurrence relation like so:
\[\begin{aligned} T(n) &= aT(\frac n b) +f(n)\\ &= a \left(aT(\frac n {b^2}) +f(\frac n b)\right)+f(n)\\ &= a^2T(\frac n {b^2}) +af(\frac n b)+f(n)\\ &= a^3T(\frac n {b^3}) + a^2f(\frac n {b^2}) +af(\frac n b)+f(n)\\ &= \ldots\\ &=a^{\log_bn}T(1)\sum^{\log_bn-1}_{j=0}a^jf(\frac n {b^i})\\ &=n^{\log_ba}T(1)\sum^{\log_bn-1}_{j=0}a^jf(\frac n {b^i})\\ \end{aligned}\]Once we have the time in this form we can make one of the following conclusions:
- If $f(n)$ is smaller than $n^{\log_ba}$, then the first term is going to dominate the summation, and we will have $T(n)=\Theta(n^{\log_ba})$.
- If there is a constant $k\geq 0$ such that $f(n)$ is $\Omega(n^{\log_ba}\log^kn)$, then $T(n)$ is $\Theta(n^{log_ba}\log^{k+1}n)$.
- If $n^{\log_ba}$ is smaller than $f(n)$, then the summation will dominate this expression and we will have $T(n)=\Theta\left(f(n)\right)$
There is a nice example of using the master method starting at slide 13.
Cammy has a video example at: https://youtu.be/Sn3D9_TmyWw.