# Master Theorem

• The Master Theorem provides us a way to solve recurrences of a very special form.

• Let $T(n) = aT \left(\dfrac{n}{b} \right) + f \left( n \right)$, where $a \geq 1, b > 1$ and $f \left( n \right)$ is asymptotically positive (positive for large $n$ as $n$ increases). If $f \left( n \right) \in \Theta \left( n^c \right)$, then

$T(n) \in \begin{cases} \Theta \left( n^{\log_b a} \right), & \text{if } a > b^c \\ \Theta \left( n^c \log n \right), & \text{if } a = b^c \\ \Theta \left( n^ c \right), & \text{if } a < b^c. \end{cases}$

• Let’s demonstrate the Master Theorem using a few examples.

• $T(n) = 4 T \left( \dfrac{n}{2} \right) + n$.

We see that $a = 4, b = 2, f(n) = n, c = 1$. The conditions of the Master Theorem are satisfied, so we can use it.

We apply case 1, since $4 > 2^1$. So $T(n) \in \Theta \left( n^{log_2 4} \right) \Rightarrow T(n) \in \Theta \left( n^2 \right)$.

• $T(n) = 4 T \left( \dfrac{n}{2} \right) + n^2$.

We see that $a = 4, b = 2, f(n) = n^2, c = 2$. The conditions of the Master Theorem are satisfied, so we can use it.

We apply case 2, since $4 = 2^2$. So $T(n) \in \Theta \left( n^2 \log n \right)$.

• $T(n) = 4 T \left( \dfrac{n}{2} \right) + n^3$.

We see that $a = 4, b = 2, f(n) = n^3, c = 3$. The conditions of the Master Theorem are satisfied, so we can use it.

We apply case 3, since $4 < 2^3$. So $T(n) \in \Theta \left( n^3 \right)$.

• $T(n) = 4 T \left( \dfrac{n}{2} \right) + \dfrac{ n^2 }{ \log n }$.

We see that $a = 4, b = 2, f(n) = \dfrac{ n^2 }{ \log n }$. The conditions of the Master Theorem are not satisfied, so we cannot proceed to use it.