Big-Ω (Omega)

If `O(n)` is the worst-case ceiling on an algorithm's running time, what tells you the floor, the absolute minimum work the algorithm must always do? That is the question **Big-Omega Notation** answers, and it is the second pillar of asymptotic analysis that turns half a description of performance into the full picture. This lesson introduces `Omega(g(n))` as a formal lower bound, with the mirror-image definition of Big-O: there exist positive constants `c` and `n0` such that `f(n) >= c * g(n)` for all `n >= n0`. You will practice proving Omega claims, analyze the best-case behavior of familiar algorithms (linear search, bubble sort, insertion sort), and meet a famous problem lower bound: any comparison-based sort must do at least `Omega(n log n)` comparisons in the worst case. You will also learn to spot when an algorithm is asymptotically optimal because its upper and lower bounds coincide. This lesson builds directly on **Big-O Notation (Upper Bound)**, where you learned to express upper bounds on growth using constants `c` and `n0`. Big-Omega flips the inequality from `<=` to `>=` and reuses the same machinery to describe floors instead of ceilings. Once you are comfortable bracketing algorithms with both bounds, you will be ready for **Big-Theta Notation (Tight Bound)**, where the upper and lower bounds meet to give the most precise complexity statement possible.

When you can say *both* that an algorithm runs in `O(n log n)` and that it must do at least `Omega(n log n)` work, the ceiling and floor have collapsed onto the same growth rate. That coincidence is the most informative complexity statement you can make, and it is what **Big-Theta Notation** captures in a single symbol. This lesson defines `Theta(g(n))` as the intersection of Big-O and Big-Omega: there exist positive constants `c1`, `c2`, and `n0` such that `c1 * g(n) <= f(n) <= c2 * g(n)` for all `n >= n0`, the so-called sandwich property. You will practice classifying functions and algorithms by their tight bound, learn when Big-Theta is appropriate (best and worst case have the same growth rate) versus when only Big-O is honest (the cases differ), and see why merge sort is `Theta(n log n)` while linear search is *not* Theta of any single function. This lesson stitches together two ideas you have already met. From **Big-O Notation (Upper Bound)** you have the ceiling `f(n) <= c * g(n)`, and from **Big-Omega Notation (Lower Bound)** you have the floor `f(n) >= c * g(n)`. Big-Theta simply requires both bounds to hold for the same `g(n)`, so an algorithm only earns a Theta label when its upper and lower bounds genuinely match. With all three asymptotic notations in hand, you will be ready to switch focus to **Memory Models**, where the same growth-rate thinking gets applied to space rather than time.

When a paper claims an algorithm runs in `O(n^2)`, that statement leaves a question wide open: does the algorithm *actually* take quadratic time, or could the bound be loose? **Little-o** and **little-omega** are the notations that close that gap. `f(n) = o(g(n))` says `f` grows *strictly* slower than `g`, never matching its rate, and `f(n) = omega(g(n))` says `f` grows strictly faster. They are the precision tools of theoretical CS. This lesson defines both notations using the formal limit-based criterion: `f(n) = o(g(n))` iff `lim f(n)/g(n) = 0`, and `f(n) = omega(g(n))` iff `lim f(n)/g(n) = infinity`. You will prove and disprove `o` and `omega` claims for common function pairs (`n` vs `n^2`, `log n` vs `n`, `n` vs `n log n`, `2^n` vs `n^k`), use these notations to rank growth rates strictly, and see how the full five-notation system fits together: `O` and `Omega` allow equality, `Theta` requires it, while `o` and `omega` forbid it. This lesson builds on three earlier asymptotic foundations. From **Big-O Notation (Upper Bound)** you have non-strict ceilings; from **Big-Omega Notation (Lower Bound)** you have non-strict floors; and from **Big-Theta Notation (Tight Bound)** you have the exact-rate case. Little-o and little-omega simply require the inequality to be strict, ruling out the matching case that Big-O and Big-Omega permit. With all five notations under your belt, you will be ready for **Complexity Classes (Conceptual Overview)**, where these comparisons get used to separate classes like `P` and `NP`.