定义

已知

• 函数 $f$ 和函数 $g$

则 $f\in O(g)$ :=

$$ \exists C>0 \ \exists k \ \forall x>k \ (\left|f(x)\right| \leq C\left|g(x)\right|) $$

aka

$$ \exists C(C>0 \land \exists k \forall x(x>k \to \left|f(x)\right| \leq C\left|g(x)\right|)) $$

性质

0. 常见函数的大 $O$ 估计排序 $\log n « n « n^{\alpha} « \alpha^{n} « n!$
1. $f_{1}+f_{2}\in O(\mathrm{max}(g_{1}, g_{2}))$
2. $f_{1} \cdot f_{2} \in O(g_{1} \cdot g_{2})$