Master Theorem

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

where $a≥1,b≥1$ be constant and $f(n)$ be a function

Let $T(n)$ is defined on non-negative integers by the recurrence

$n$ is the size of the problem
$a$ is the number of sub problems in the recursion
$\frac{n}{b}$ is the size of each sub problem (Here it is assumed that all sub problems are essentially the same size)
$f(n)$ is the time to create the sub problems and combine their results in the above procedure

There are following three cases:

If $f(n)=\Theta(n^c)$ where $c < log_ba$ then $\color{red}{T(n)=\Theta(n^{log_ba})}$
If $f(n)=\Theta(n^c)$ where $c=log_ba$ then $\color{red}{T(n)=\Theta(n^clogn)}$
If $f(n)=\Theta(n^c)$ where $c>log_ba$ then $\color{red}{T(n)=\Theta(f(n))}$

$$ T(n)=\color{red}{2^n}T(\frac{n}{2}) + n $$

$a$ is not constant. The number of subproblems should be fixed

$$ T(n)=\color{red}{0.5}{T(\frac{n}{2})+n} $$

$a< 1$. Can't have less than 1 subproblems

$$ T(n)=16T(\frac{n}{2})\color{red}{-n^2} $$

$f(n)$ which is the combination time is not positive