Big-Omega Notation Ω-notation

Big-Omega Notation (Ω-notation)

Big-O tells you how bad an algorithm can get; Big-Omega (Ω) tells you how good it can never get better than. It is a lower bound on growth. If Big-O is the ceiling a function stays under, Ω is the floor it stays above. When we say an algorithm is Ω(n), we are promising that for large inputs it will do at least some constant multiple of n work — no clever trick will make it fundamentally cheaper than linear.

The key mental shift: O and Ω are about the same function’s growth, bounding it from two sides. They are not shorthand for “worst case” and “best case” — that is a common confusion we untangle below.

Precise definition

We say f(n) = Ω(g(n)) if there exist positive constants c and n0 such that:

0 ≤ c·g(n) ≤ f(n)   for all   n ≥ n0

Read literally: past some starting point n0, the function f(n) sits on or above the curve c·g(n). The constant c lets us ignore multiplicative factors; n0 lets us ignore small-n noise where cheaper terms might dominate.

Contrast the trio:

• O(g) — upper bound: f grows no faster than g.
• Ω(g) — lower bound: f grows no slower than g.
• Θ(g) — tight bound: f is both O(g) and Ω(g); it grows exactly like g.

So Θ is the intersection: f = Θ(g) iff f = O(g) and f = Ω(g).

Worked example: linear search, counted

Consider scanning an array of n items for a target, one comparison per element until found:

• Best case (target at index 0): 1 comparison, regardless of n.
• Worst case (target at the end, or absent): n comparisons.

Now bound the worst-case count function Tworst(n) = n. Is it Ω(n)? Pick c = 1, n0 = 1: then 1·n ≤ n holds for all n ≥ 1. Yes — the worst case is Ω(n). It is also O(n), so it is Θ(n).

But here is the subtlety interviewers love. The best-case count is Tbest(n) = 1. Is 1 = Ω(n)? We would need c·n ≤ 1 for all large n — impossible for any positive c, since c·n grows without bound. So the best case is not Ω(n); it is Ω(1). Every case, best or worst, has its own O and Ω bounds. That is why “Ω = best case” is wrong.

Concretely at n = 1000: worst case does 1000 comparisons (Ω(n) floor holds), best case does 1 (no linear floor possible).

Pitfalls and what an interviewer probes

• Confusing Ω with best case. Ω bounds a chosen function from below; you can talk about the Ω of the best case, the worst case, or the average. Bound and case are independent axes.
• Loose but true bounds. Every function is Ω(1) (it does at least constant work), and any O(n²) algorithm is trivially Ω(1). Saying “mergesort is Ω(1)” is technically true but useless. Interviewers want the tightest honest bound — ideally Θ.
• Claiming a lower bound for a whole problem vs an algorithm. “Comparison sorting is Ω(n log n)” is a statement about every possible algorithm for the problem, proved via decision trees — far stronger than bounding one implementation. Know which you are asserting.
• Direction of the inequality. Under pressure people flip c·g(n) ≤ f(n). For Ω, g is underneath.

When it matters in practice

Ω earns its keep in two places. First, impossibility arguments: a lower bound proves no algorithm can beat a threshold, so you stop hunting for one. The Ω(n log n) barrier for comparison sorts is why practitioners reach for O(n) tricks like counting/radix sort only when keys are bounded integers — they sidestep the comparison model entirely.

Second, honest expectation-setting. If an operation is Ω(n), you know that caching, better constants, or SIMD will shave factors but never change the shape — you must reduce the input or change the algorithm class to win asymptotically.

Trade-off against neighbours: O alone can lull you (“it’s O(n²)” might actually always run in n²). Θ is what you usually want to report because it pins growth on both sides. Reach for a bare Ω when you can only honestly prove a floor — often the hardest and most valuable thing to establish about a problem.

Key takeaways

• Ω is a lower bound: f = Ω(g) means c·g(n) ≤ f(n) for all n ≥ n0 — f grows no slower than g.
• Ω is not “best case.” Best, worst, and average each have their own O, Ω, and Θ; bound and case are separate axes.
• Θ = O and Ω together; report Θ when you can, and always give the tightest honest Ω, since Ω(1) is trivially true and unhelpful.
• Problem-level lower bounds (e.g. comparison sorting is Ω(n log n)) prove no algorithm can do better — a stronger, more useful claim than bounding one implementation.