next up previous
Next: 1.2.7 An Example: Up: 1.2 Complexity of Algorithms Previous: 1.2.5 Worst Case, Average Case, and Amortized Complexity

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 n0 such that

f (n) $\displaystyle \geq$ Cg(n)   $\displaystyle \forall$  n $\displaystyle \geq$ n0

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

f (n) $\displaystyle \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 C1 and C2 and a positive integer n0, such that

C1g(n) $\displaystyle \leq$ f (n) $\displaystyle \leq$ C2g(n)   $\displaystyle \forall$ n $\displaystyle \geq$ n0