定理1
定理 设 f 和 g是定义域为自然数集合的函数.
(1)如果 %2Fg(n))
存在, 并且等于某个常数c>0, 那么 f(n) = 
(g(n)).
(2)如果 =0，那么f(n) = o(g(n)).
(3)如果 =+∞，那么f(n) = ω(g(n)).
证明用到
,
定义
证明定理1(1)
根据极限定义，对于给定正数 ε 存在某个，
只要n ≥ ，就有
| f(n)/g(n)-c | < ε
c -ε < f(n)/g(n) < c +ε
c/2 < f(n)/g(n) < 3c/2 < 2c
对所有n≥, f(n)≤ 2cg(n), 于是 f(n)=O(g(n))；
取ε =c/2,
对所有n≥, f(n)≥(c/2)g(n),于是 f(n)=Ω(g(n)).
从而 f(n) = (g(n))
例：估计函数的阶
例1 设 f (n) = , 证明 f(n) =
.
证 因为
根据定理1，有
一些重要结果
可证明：多项式函数的阶低于指数函数的阶
证 不妨设d为正整数
分子分母求导数
定理 2
定理 设函数f, g, h的定义域为自然数集合，
(1) 如果 f=O(g) 且 g=O(h)，那么 f=O(h).
(2)如果 f=Ω(g) 且 g=Ω(h)， 那么 f =Ω (h).
(3)如果 f=(g) 和 g=
(h)， 那么 f =
(h).
函数的阶之间的关系具有传递性
例子
按照阶从高到低排序以下函数：
h(n) = ω(f(n))，
f(n) = ω(g(n)),
g(n) = ω(t(n)),
排序
定理3
定理 假设函数f 和g的定义域为自然数集，
若对某个其它函数h, 有 f =O(h) 和 g=O(h)，
那么f + g = O(h).该性质可以推广到有限个函数.算法由有限步骤构成. 若每一步的时间复杂度函数的上界都是h(n)，那么该算法的时间复杂度函数可以写作O(h(n)).
