定义

$O$ 符号

定义：令 $f(n)$ 和 $g(n)$ 是从自然数集到非负实数集的两个函数，如果存在一个自然数 $n_0$ 和一个常数 $c>0$，使得

$$\forall n \geq n_0,\ f(n) \leq cg(n)$$

称 $f(n)$ 为 $O(g(n))$.

$\Omega$ 符号

定义：令 $f(n)$ 和 $g(n)$ 是从自然数集到非负实数集的两个函数，如果存在一个自然数 $n_0$ 和一个常数 $c>0$，使得

$$\forall n \geq n_0,\ f(n) \geq cg(n)$$

称 $f(n)$ 为 $Omega(g(n))$.

$\Theta$ 符号

定义：令 $f(n)$ 和 $g(n)$ 是从自然数集到非负实数集的两个函数，如果存在一个自然数 $n_0$ 和两个正个常数 $c_1, c_2$，使得

$$\forall n \geq n_0,\ c_1g(n) \leq g(n) \leq c_2g(n) $$

称 $f(n)$ 为 $Theta(g(n))$.

这个定义有个重要的推论：
$f(n) = Theta(g(n))$，当且仅当 $f(n) = O(g(n))$ 且 $f(n) = Omega(g(n))$.

举例