マスター定理

$a \ge 1$、$b > 1$ を実数、$d > 0$ を定数とし、$f$ を $b$ のべき乗の上で定義された正の値をとる関数とする。関数 $T$ が

を満たすとする。$n$ は $b$ のべき乗の上を動くものとして、次が成り立つ。

1. ある $\varepsilon > 0$ について $f(n) = O\!\left(n^{\log_b a - \varepsilon}\right)$ ならば、$T(n) = \Theta\!\left(n^{\log_b a}\right)$。
2. $f(n) = \Theta\!\left(n^{\log_b a}\right)$ ならば、$T(n) = \Theta\!\left(n^{\log_b a}\log n\right)$。
3. ある $\varepsilon > 0$ について $f(n) = \Omega\!\left(n^{\log_b a + \varepsilon}\right)$ であり、かつある定数 $0 < c < 1$ が存在してすべての $k \ge 1$ で $a\,f(b^{k-1}) \le c\,f(b^{k})$（正則条件）が成り立つならば、$T(n) = \Theta(f(n))$。