📖 Master theorem: Let $a,C>0$ and $b\ge 0$ be constants and $T:\mathbb{N}⟶{\mathbb{R}}^{+}$ a function such that for all even $n\in \mathbb{N}$,

$$T(n)\le aT(n/2)+C{n}^b.$$

Then for all $n=2^k,k\in \mathbb{N}$,

• If $b>{\log }_{2}a,T(n)\le O(n^b)$.
• If $b={\log }_{2}a,T(n)\le O(n^{{\log }_{2}a}\cdot \log n)$.
• If $b<{\log }_{2}a,T(n)\le O(n^{{\log }_{2}a})$.

If the function $T$ is increasing, then the condition $n=2^k$ can be dropped. If the master inequality holds with $=$, then we may replace $O$ with $\Theta$ in the conclusion.