1.2.6 Big Omega and Big Theta Notations

The $\Omega$ notation specifies asymptotic lower bounds.

DEF. Big Omega. f (n) is said to be $\Omega$(g(n)) if $\exists$ a positive real constant C and a positive integer n₀ such that

f (n) $$\geq$$ Cg(n)   $$\forall$$  n $$\geq$$ n₀

An Alternative Definition : f (n) is said to be $\Omega$(g(n)) iff $\exists$ a positive real constant C such that

f (n) $$\geq$$ Cg(n)  for infinitely many values of n.

The $\Theta$ notation describes asymptotic tight bounds.

DEF. Big Theta. f (n) is $\Theta$(g(n)) iff $\exists$ positive real constants C₁ and C₂ and a positive integer n₀, such that

C₁g(n) $$\leq$$ f (n) $$\leq$$ C₂g(n)   $$\forall$$ n $$\geq$$ n₀