big Omega notation

A way of writing a lower bound: Omega(f(n)) means the cost grows at least as fast as a constant times f(n) for large n.

In more detail

Where Big O caps the cost from above, Omega guarantees a floor. The best case of linear search is Omega(1), because finding the target in the first slot costs one comparison. The lower bound for comparison sorting, Omega(n log n), says that no comparison-based sort can do better in the worst case.

Related terms

Taught in

References