Master Theorem

The master theorem provides a general boilerplate solution for solving recurrence relations (like divide and conquer algorithms) that satisfy a particular format.

Definition

Let $f$ be an increasing function satisfying a recurrence relation:

$f(n)=af\left(\frac{n}{b}\right)+c{n}^d$

Whenever

• $n=b^k$ for some $k\ge 1$, $a\ge 1$
• $b$ is an integer > 1
• $c$ and $d$ are real numbers ≥ 0

Then

$f(n)=af\left(\frac{n}{b}\right)+c{n}^d=\{\begin{array}{ll}\mathrm{\Theta }\left(n^d\right)& a<b^d\\ \mathrm{\Theta }(n^d\log n)& a=b^d\\ \mathrm{\Theta }\left(n^{{\log }_{b}a}\right)& a>b^d\end{array}$

Proof

Proposition. If $a=b^d$ and $n$ is a power of $b$, then a function $f$ satisfying the recurrence relation $f(n)=af(n/b)+c{n}^d$ is of the form $f(n)=f(1)n^d+c{n}^d{\log }_{b}n$

Proof. Let $k={\log }_{b}n$. Then

$\begin{array}{rl}f(n)& =c{n}^d+ac{\left(\frac{n}{b}\right)}^d+a^{2}c{\left(\frac{n}{b^2}\right)}^d+\dots +a^{k-1}c{\left(\frac{n}{b^{k-1}}\right)}^d+a^{k}f(1)\\ & =a^{k}f(1)+\sum _{j=0}^{k-1}{a}^{j}c{\left(\frac{n}{b^j}\right)}^d\\ & =a^{k}f(1)+\sum _{j=0}^{k-1}c{n}^d\\ & =a^{k}f(1)+kc{n}^d\\ & =a^{{\log }_{b}n}f(1)+c({\log }_{b}n)n^d\\ & =b^{d{\log }_{b}n}f(1)+c({\log }_{b}n)n^d\\ & =n^{d}f(1)+c({\log }_{b}n)n^d\\ & =O(n^d\log n)\end{array}$