Master Theorem

The Master Theorem provides a solution to the time complexity of recurrence relations 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}$$

Recurrence relation

The recurrence relation describes an algorithm that divides a problem of size $n$ into $a$ subproblems, each of size $\frac{n}{b}$, and solves them recursively. (Note that $\frac{n}{b}$ may not be an integer, but it is proven that replacing $T(n/b)$ with $T(\lfloor n/b\rfloor )$ or $T(\lceil n/b\rceil )$ does not affect the asymptotic behaviour)

Only works for divide and conquer

Where

$a$ is number of subproblems or sub calls per call $\frac{n}{b}$ is the size of input each subproblem receives $k\cdot n^c$ represents the time complexity of one recursion