Little Omega Notation

The little ω notation is used to describe the asymptotic efficiency of algorithms. It is written ω(f(n)) where n∈N (sometimes sets other than the set of natural numbers, N, are used).

The expression ω(f(n)) is the set of functions {g(n):∀c∈N, c>0, ∃n0∈N ∀n≥n0, 0≤cf(n)≤g(n)}. In plain English, this set is populated by functions that are bounded cf(n). This is known as an asymptotic lower bound. The fact that this holds for all c means that this bound is not asymptotically tight. This should be compared with the big omega notation. For set membership, we write h(n)=ω(f(n)) and not h(n)∈ω(f(n)).

Examples

• 2≠ω(1)
• 4x+2≠ω(x)
• 4x+2=ω(1)
• 3x2+4x+2≠ω(x2)
• 3x2+4x+2=ω(x)

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.