Master Theorem

The Master Theorem provides a solution to the runtime of divide-and-conquer algorithms of the form

$$T(n)=\{\begin{array}{ll}aT(\frac{n}{b})+k{n}^c& \text{if }n>1\\ d& \text{if }n=1\end{array}\text{where}a>0,b>1,c\ge 0,d\ge 0,k>0$$

where the solution is

$$T(n)=\{\begin{array}{ll}O(n^c)& \text{if }a<b^c\\ O(n^{c}logn)& \text{if }a=b^c\\ O(n^{lo{g}_b(a)})& \text{if }a>b^c\end{array}$$