Master Theorem

The master theorem is used to calculate the worst case complexity of Recurrence Equations of the form:

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

Where $a\ge 1$ and $b\ge 1$ and $f(n)$ is an asymptotically positive function.

Note

It is important to note that $\frac{n}{b}$ is not always an integer. This is why it is usually in form $\lceil \frac{n}{b}\rceil$.

It can be used on three cases:

1. $f(n)=O(n^{lo{g}_{b}a-ϵ})$ (Big-Oh Notation), where $ϵ>0$. $T(n)=\Theta (n^{lo{g}_{b}a})$
2. $f(n)=\Theta (n^{lo{g}_{b}a})$ (Big-Theta Notation), then $T(n)=\Theta (n^{lo{g}_{b}a}logn)$
3. $f(n)=\Omega (n^{lo{g}_{b}a-ϵ})$ (Big-Omega Notation), where $ϵ>0$. $T(n)=\Theta (f(n))$