1. Ο符号,表示一个上界
f(n)=Ο(g(n)) means there are consts c>0,n0>0,such that 0 <= f(n) <= c g(n) for all n>=n0, ex : 2n² = O(n³)
Other Ex:
f(n) = n³+O(n²) means an error term
n²+Ο(n)=O(n²) means for any f(n)∈Ο(n)
here is an h(n)∈O(n²) such that n²+f(n)=h(n)
2. Ω符号 表示一个下界
f(n)=Ω(g(n)):
there exist consts c>0,n0>0,such that 0<=cg(n)<f(n)
for all n>= n0
Ex: n½ = Ω(㏒n)
3. Θ符号 表示一个集合
f(n)=Θ(g(n)):
means there are consts c1,c2>0,such that
c1g(n)<=f(n)<=c2g(n) for all n>0
4. ο符号
f(n)=ο(g(n)) means: lim(n->∞) f(n)/g(n) = 0;
5. ω符号
f(n)=ω(g(n)) means: lim(n->∞) f(n)/g(n) = ∞;
