Master Theorem

The master theorem for divide-and-conquer recurrences provides an asymptotic analysis for many recurrence relations that occur in the analysis of divide-and-conquer algorithms.

Consider a problem that can be solved using a recursive algorithm such as the following:

$$\begin{array}{rl}& \text{Procedure}\mathrm{p}(\text{input }x\text{ of size }n)\\ & \text{If }n<\text{some constant }k\text{ then:}\\ & \text{Solve }x\text{ directly without recursion}\\ & \text{Else:}\\ & \text{Create }a\text{ subproblems of }x,\text{each having size }\frac{n}{b}\\ & \text{Call procedure p recursively on each subproblem}\\ & \text{Combine the results from the subproblems}\end{array}$$

If each dividing and combining process of size $n$ takes a time of $f(n)$, the runtime of the algorithm can be expressed by the recurrence relation

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

The master theorem indicates that, for constants $a\ge 1$ and $b>1$ with $f$ asymptotically positive, the following statements are true:

• Case 1. If $f(n)=O\left(n^{{\log }_{b}a-\epsilon }\right)$ for sone $\epsilon >0$, Then $T(n)=\Theta \left(n^{{\log }_{b}a}\right)$
• Case 2. If $f(n)=\Theta \left(n^{{\log }_{b}a}\right)$, then $T(n)=\Theta \left(n^{{\log }_{b}a}\log n\right)$
• Case 3. If $f(n)=\Omega \left(n^{{\log }_{b}a+\epsilon }\right)$ for some $\epsilon >0$ (and $af\left(\frac{n}{b}\right)\le cf(n)$ for some $c<1$ for all $n$ sufficiently large), then $T(n)=\Theta (f(n))$

Furthermore, if we are in Case 1 when $n=b^k$ and $a\ne 1$, then

$$f(n)=C_1{n}^{{\log }_{b}a}+C_2$$

where $C_1=f(1)+\frac{c}{a-1}$ and $C_2=-\frac{c}{a-1}$