入力を 2 倍にしたときの比

$\alpha > 0$、$\beta$ を定数、$k > 0$ を実数とする。次が成り立つ。

1. $T(n) = \alpha$ ならば $T(2n)/T(n) = 1$。
2. $T(n) = \alpha \log_2 n + \beta$ ならば $T(2n) - T(n) = \alpha$（比ではなく差が一定）。
3. $T(n) = \alpha n^{k}$ ならば $T(2n)/T(n) = 2^{k}$。
4. $T(n) = \alpha n \log_2 n$ ならば $T(2n)/T(n) = 2\left(1 + \dfrac{1}{\log_2 n}\right)$ であり、$n \to \infty$ で $2$ に収束する。
5. $T(n) = \alpha\, 2^{n}$ ならば $T(2n)/T(n) = 2^{n}$。