O 記法の計算則

$f, f_1, f_2, g, g_1, g_2, h$ を非負実数値関数とする。次が成り立つ。

1. （反射律）$f \in O(f)$。
2. （推移律）$f \in O(g)$ かつ $g \in O(h)$ ならば $f \in O(h)$。
3. （定数倍）$\lambda > 0$ かつ $f \in O(g)$ ならば $\lambda f \in O(g)$。
4. （和）$f_1 \in O(g_1)$ かつ $f_2 \in O(g_2)$ ならば $f_1 + f_2 \in O(\max(g_1, g_2))$。ここで $\max(g_1,g_2)$ は各点ごとの最大値を取る関数である。
5. （積）$f_1 \in O(g_1)$ かつ $f_2 \in O(g_2)$ ならば $f_1 f_2 \in O(g_1 g_2)$。