3. The Master Theorem

The Master Theorem

The Master Theorem states that for some $T(n)$ which is a monotonically increasing recurrence relation such that:

$$\begin{array}{c}T(n)=a\cdot T\left(\begin{array}{c}\lceil \frac{n}{b}\rceil \end{array}\right)+f(n)\\ \text{where }a\ge 1,b\ge 2\end{array}$$

Then we know that:

$$\begin{array}{c}T(n)=\{\begin{array}{ll}\Theta (n^k)& \text{if }f(n)\in O(n^{k-ϵ})\\ \Theta (n^k{\log }_{2}n)& \text{if }f(n)\in \Theta (n^k)\\ \Theta (f(n))& \text{if }f(n)\in \Omega (n^{k+ϵ}){}^{†}\end{array}\\ \text{for some }ϵ>0,\text{where }k={\log }_{b}a\end{array}$$

$\text{† Must satisfy regularity condition, in supplementary reading.}$

Link to original

Example 1: Calculate the growth rate of $T(n)$.

Let $T(n)$ be a recurrence relation defined by:

$$\begin{array}{c}T(1)=1,T(n)=9\cdot T\left(\begin{array}{c}\lfloor \frac{n}{3}\rfloor \end{array}\right)+\sqrt{(n+1{)}^5}\\ \text{for all }n>1\end{array}$$

1. Identify the parameters: $a=9$, $b=3$ hence $k={\log }_3(9)=2$
2. Identify the growth rate of $f(n)$: $f(n)=\sqrt{(n+1{)}^5}=n^{2.5}+[\dots ]\in \Theta (n^{2.5})$
3. Identify the case: The growth rate of $f(n)\in \Omega (n^{k+ϵ})$, hence we have that $T(n)=\Theta (f(n))$. $\therefore$ by Master Theorem, $T(n)=\Theta (n^{2.5})$.

Example 2: Calculate the growth rate of $T(n)$.

Let $T(n)$ be a recurrence relation defined by:

$$\begin{array}{c}T(1)=1,T(n)=2\cdot T\left(\begin{array}{c}\lceil \frac{n}{2}\rceil \end{array}\right)+n\\ \text{for all }n>1\end{array}$$

1. Identify the parameters: $a=2$, $b=2$ hence $k={\log }_2(2)=1$
2. Identify the growth rate of $f(n)$: $f(n)=n\in \Theta (n)$
3. Identify the case: The growth rate of $f(n)\in \Theta (n^k)$, hence we have that $T(n)=\Theta (n^k{\log }_{2}n)$. $\therefore$ by Master Theorem, $T(n)=\Theta (n{\log }_{2}n)$.

Example 3: Calculate the growth rate of $T(n)$.

Let $T(n)$ be a recurrence relation defined by:

$$\begin{array}{c}T(1)=1,T(n)=3\cdot T\left(\begin{array}{c}\lceil \frac{n}{2}\rceil \end{array}\right)+{\log }_2(5n^2)\\ \text{for all }n>1\end{array}$$

1. Identify the parameters: $a=3$, $b=2$ hence $k={\log }_3(2)\approx 1.5849$
2. Identify the growth rate of $f(n)$: $f(n)={\log }_2(5n^2)\in \Theta ({\log }_{2}n)$
3. Identify the case: The growth rate of $f(n)\in O(n^k)$, hence we have that $T(n)=\Theta (n^k)$. $\therefore$ by Master Theorem, $T(n)=\Theta (n^{{\log }_3(2)})$.