以下内容摘录自《数据结构与算法分析C++描述》：
本书将使用下列四个定义：
定义2.1 如果存在正常数c和n0使得使得当N>=n0时T(N)<=cf(N),则记为T(N) = O(f(N))。
定义2.2 如果存在正常数c和n0使得使得当N>=n0时T(N)>=cg(N),则记为T(N) = Ω(g(N))。
定义2.3 T(N) = θ(h(N)) 当且仅当T(N) = O(h(N)) 和 T(N) = Ω(h(N))。
定义2.4 如果对所有的常数c存在n0使得当N>n0时T(N)<cp(N)，则记为T(N) = o(p(N))。
这些定义的目的是要在函数间建立一种相对的级别。给定两个函数，通常存在一些点，在这些点上一个函数的值小于另一个函数的值。因此，像f(N) < g(N)这样的声明是没有什么意义的。于是，我们比较它们的相对增长率。
当我们说T(N) = O(f(N))时，我们是在保证函数T(N)是在以不快于f(N)的速度增长；因此f(N)是T(N)的一个上界。由于这意味着f(N) = Ω(T(N))，于是我们说T(N)是f(N)的一个下界。
我们需要掌握的重要结论为：
法则1 如果T1(N) = O(f(N))且T2(N) = O(g(N))，那么
（a）T1(N) + T2(N) = O( f(N) + g(N) )
（b）T1(N)T2(N) = O( f(N)g(N) )
法则2 如果T(N)是一个k次多项式，则T(N) = θ(N^k)。
法则3 对任意常数k，log^k (N) = O(N)。它告诉我们对数增长得非常缓慢。
首先，将常数或低阶项放进大O是非常不好的习惯。
其次，我们总能够通过计算极限limn→∞f(N)/g(N)来确定两个函数f(N)和g(N)的相对增长率，必要时可以使用洛必达法则。
对诸如冒泡排序这样的简单排序算法，当输入量增加到2倍的时候，对大量输入来说，运行时间则增长到4倍。这是因为这些算法不是线性的。这讨论排序时，我们将会看到，不好的排序算法是O(N^2)。