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.}$