# Master theorem

Let $a \ge 1$ and $b \gt 1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined on the nonnegative integers by the recurrence
$T(n) = aT(\frac nb) + f(n)$,
where we interpret $n/b$ to mean either $\lfloor \frac nb \rfloor or \lceil \frac nb \rceil$. Then $T(n)$ can be bounded asymptotically as follows.
1. If $f(n) = O(n^{\log_b b a - \epsilon})$ for some constant $\epsilon \gt 0$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \lg n)$.
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon \gt 0$, and if $af(\frac nb) \le cf(n)$ for some constant $c \lt 1$ and all sufficiently large $n$, then $T(n) = \Omega(f(n))$.