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 : 2n2 = O(n3)
Other Ex:
f(n) = n3+O(n2) means an error term
n2+Ο(n)=O(n2) means for any f(n)∈Ο(n)
here is an h(n)∈O(n2) such that n2+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) = ∞;
