Θ(g(n))={ f(n)：存在正常数c1,c2和n0，使对所有的n>=n0，有0<=c1g(n)<=f(n)<=c2g(n) }
(在集合表示法中，“：”应读作“满足......的特性”)
渐进上界O
O(g(n))={ f(n)：存在正常数c和n0，使对所有n>=n0，有0<=f(n)<=cg(n) }
渐进下界Ω
Ω(g(n))={ f(n)：存在正常数c和n0，使对所有n>=n0，有0<=cg(n)<=f(n) }
非渐进紧确的上界o
其中，O记号所提供的渐进上界可能是也可能不是渐进紧确的。我们使用o记号表示非渐进紧确的上界：
o(g(n))={ f(n)：对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0<=f(n)<=cg(n) }
非渐进紧确的下界ω
ω记号与Ω记号的关系就好像o记号与O记号的关系一样。我们用ω记号来表示非渐进紧确的下界:
ω(g(n))={ f(n)：对任意正常数c，存在常数n0>0，使对所有的n>=n0，有0<=cg(n)<f(n) }
或者另一种定义为
f(n)∈ω(g(n))当且仅当g(n)∈o(f(n))
![Image[5]](http://images0.cnblogs.com/blog/482227/201303/28202512-61ecdb33521b49d0b0b06c081e5a1014.png "Image[5]")
记号Θ，O和Ω的图例。在每个部分中，n0是最小的可能值；大于n0的值也有效。
a）Θ记号限制一个函数在常数因子内。如果存在正常数n0，c1和c2使得在n0右边 f(n)的值永远在c1g(n)与c2g(n)之间，那么可以写成f(n)=Θ(g(n))。
b）O记号给出一个函数在常数因子内的上限。如果存在正常数n0和c使得在n0右边 f(n)的值永远等于或小于cg(n)，那么可以写成f(n)=O(g(n))。
c）Ω记号给出一个函数在常数因子内的下限。如果存在正常数n0和c使得在n0右边 f(n)的值永远等于或大于cg(n)，那么可以写成f(n)=Ω(g(n))。