Big-Omega as a lower bound
/ big oh-MAY-guh /
Big-Omega is the floor that mirrors Big-O's ceiling. When we say a cost is Omega(n log n), we are promising that, for large inputs, it is at least some constant multiple of n log n — it cannot do better than that. It is the 'this will take at least an hour' counterpart to 'at most three hours'.
Formally, f(n) is Omega(g(n)) if there exist a positive constant c and a threshold n0 such that f(n) >= c times g(n) for every n >= n0. Same two witnesses as Big-O, but the inequality flips direction. For example, n^2 - 3n is Omega(n^2): pick c = 1/2 and n0 = 6, and for all n >= 6 we have 3n <= (1/2)n^2 (since n >= 6 means n/2 >= 3), so n^2 - 3n >= n^2 - (1/2)n^2 = (1/2)n^2 = c times n^2. We bounded the subtracted term from above to leave a clean fraction of n^2 behind.
Big-Omega is the natural language for lower bounds, both for a particular algorithm ('this loop alone already does Omega(n) work, so the whole thing cannot be sublinear') and for a problem ('any comparison-based sort needs Omega(n log n) comparisons, so no clever trick beats that within the comparison model'). Be careful about scope: a problem lower bound says every algorithm must pay at least this much; an algorithm's own Omega bound only describes that one algorithm. Saying f is Omega(g) is exactly the same as saying g is O(f).
Claim: any algorithm that prints all n^2 entries of an n-by-n table is Omega(n^2), because it must perform at least one output step per entry, and there are n^2 entries. No matter how clever it is, it cannot beat n^2 steps — printing the answer alone costs that much.
An output-size argument is the simplest lower bound: you must at least produce the answer.
A lower bound ON A PROBLEM (every algorithm must pay this) is much stronger and harder to prove than a lower bound on one specific algorithm. Do not confuse the two.