Big-Omega Notation

Big-Omega notation gives a lower bound on a function's growth, stating the cost is at least a certain rate.

The idea

Where big-O caps growth from above, big-Omega bounds it from below. We write f(n) = Omega(g(n)) to say f grows at least as fast as g, up to a constant factor, for large inputs. It is the tool for saying a problem or algorithm cannot be faster than some rate.

Formal definition

f(n) = Omega(g(n)) if there exist positive constants c and n0 such that f(n) >= c * g(n) for all n >= n0. It is the mirror image of the big-O inequality, with the direction of the comparison reversed.

Lower bounds on problems

Big-Omega is most powerful when applied to a problem, not just one algorithm. Any comparison-based sort must make Omega(n log n) comparisons in the worst case, because there are n! possible orderings and each comparison distinguishes at most a factor of two. No clever code beats this bound within the comparison model.

Best case versus lower bound

A common confusion: big-Omega is not the same as best case. Best case describes one favorable input. A big-Omega bound on the worst case describes a floor that holds no matter how the algorithm is written. Keep the two ideas separate.

• O: at most this fast (upper bound)
• Omega: at least this fast, i.e. no faster (lower bound)
• Theta: exactly this rate (both bounds match)

Why it matters

Lower bounds tell you when to stop optimizing. If a task provably requires Omega(n) time because it must read all n inputs, no algorithm can be sublinear, and effort is better spent elsewhere. Matching an upper bound to a lower bound, as in big-Theta, proves an algorithm is asymptotically optimal.