Big omega (written with a ) states that:

is equal to the set of functions: where there exist constants and such that for all

It represents the lower bound of a function, and corresponds to the Best Case running time.

Hint

Big-Omega can be thought of as a comparison. In other words the best case running time will always be less than or equal to the real running time.

Session 3 - Omega Definition.png#invert

Big-Omega Notation