One bound is not the whole story
In the previous guide we used Big-O to put a ceiling over a running time: T(n) = O(f(n)) promises that for large enough n, T never climbs above some constant multiple of f. That is genuinely useful, but it is only half a description. Saying "my algorithm is O(n^2)" rules out the catastrophes above n^2, yet it says nothing about whether the work could secretly be much cheaper. A ceiling alone leaves the floor unspoken.
Worse, Big-O is happy to be loose. An algorithm that truly runs in Theta(n) time is also, correctly, O(n^2) and O(n^3) and O(2^n) — every one of those is a valid (if useless) upper bound, because a true ceiling is allowed to sit far above the real cost. So when someone reports only a Big-O, you cannot tell whether they nailed the growth or just stated something safe and slack. To pin a running time down, we need a tool that pushes from below.
Omega: a floor under the growth
Big-Omega is the mirror image of Big-O. We write T(n) = Omega(g(n)) to mean that, for large enough n, T is at least a constant multiple of g — the running time can never sink below that floor. Formally it reuses the very same witness constants idea, just with the inequality flipped: there exist constants c > 0 and n0 such that T(n) >= c * g(n) for all n >= n0. Big-O bounds you from above with T(n) <= c * f(n); Omega bounds you from below.
A concrete picture: scanning an unsorted array to find its maximum must look at every element at least once, so its running time is Omega(n). No matter how clever you are, you cannot certify the maximum after inspecting only half the entries — the one you skipped could have been the largest. That Omega(n) is a statement about effort that cannot be avoided, which is exactly why lower bounds feel different from upper bounds: an upper bound is a promise about one algorithm, while a lower bound often speaks to what any honest method must pay.
Theta: squeezed from both sides
When a ceiling and a floor have the same shape, they trap the running time in a corridor — and that is Big-Theta. We write T(n) = Theta(g(n)) to mean T(n) = O(g(n)) and T(n) = Omega(g(n)) at once. Unpacked, there exist positive constants c1, c2 and a threshold n0 such that c1 * g(n) <= T(n) <= c2 * g(n) for all n >= n0. The function T is sandwiched between two parallel copies of g, never escaping above or below, so g captures its true growth rate up to constant factors.
Theta is the honest, most informative verdict, and it is the one you should aim for. Consider summing the numbers 1 to n in a single loop: each iteration costs a bounded amount of work and you run exactly n of them, so the cost is at most c2 * n (an O(n) ceiling) and at least c1 * n (an Omega(n) floor). Both halves hold, so the loop is Theta(n) — not merely O(n^2) and not merely Omega(1). When O and Omega meet on the same g, you have learned the growth, not just a safe bound.
The strict cousins: little-o and little-omega
Big-O and Big-Omega allow the bound to be tight: n is O(n) and also Omega(n), with equality of growth permitted. Their lowercase cousins forbid that touching. Little-o, written T(n) = o(g(n)), says T grows strictly slower than g — g eventually leaves T behind by any factor you like. So n = o(n^2), but n is NOT o(n), because n does not pull away from itself. Symmetrically, little-omega, T(n) = w(g(n)), says T grows strictly faster than g, the floor that g is left infinitely far beneath.
The cleanest way to feel the difference is the limit view. If the ratio T(n) / g(n) tends to 0 as n grows, then T = o(g): g overwhelms T. If the ratio tends to infinity, then T = w(g). And if the ratio settles toward a positive constant — neither vanishing nor exploding — then T = Theta(g), the two functions marching in lockstep. The limit is not the official definition (those constant-and-threshold definitions are), but when the limit exists it is a fast and reliable shortcut.
Putting the bounds to work on loops
These notations earn their keep when you read running time off real code. The companion guide on counting loop iterations gives the mechanics; here is the bound-finding mindset. For a flat loop running n times with bounded work inside, both ceiling and floor are linear, so it is Theta(n). For two nested loops each running up to n times, the body fires about n^2 times, and again both bounds match — Theta(n^2). The pattern: count the iterations, and if the count is pinned from above and below by the same function, you have a Theta.
Watch out for triangular loops, where the inner range depends on the outer index. If the inner loop runs i times when the outer index is i, the total is sum from i=1 to n of i = n(n+1)/2. That is Theta(n^2): the leading term n^2/2 fixes the growth, while the constant 1/2 and the lower-order n/2 are exactly the dust asymptotics asks us to drop. The loop body fires only about half as often as a full n-by-n nest, yet half of n^2 is still Theta(n^2) — constants do not change the class.
- Count, as a function of n, how many times the innermost work runs — a single number or a clean sum like sum from i=1 to n of i.
- Find an upper bound by overcounting: bound the inner range by its largest value to get an O(...) ceiling.
- Find a lower bound by undercounting: keep only a constant fraction of the iterations that you can guarantee always happen, to get an Omega(...) floor.
- If the ceiling and floor land on the same function g, declare Theta(g); if they differ, report the O and Omega separately and admit the gap.
Honest cautions about bounds
First, do not confuse a bound's direction with best- and worst-case. Omega means "floor on growth"; it does NOT mean "best case". You can speak of the worst case of an algorithm and bound it from above with O or below with Omega, and likewise for the best case. Saying "insertion sort is Omega(n)" reports a floor that holds for every input (it must scan the whole array), whereas its worst case is Theta(n^2) and its best case, on already-sorted input, is Theta(n). Direction of the bound and which case you analyse are two independent axes.
Second, all three notations live in the world of large n. A Theta(n^2) tag describes scaling, not a verdict at every size: because the definitions only kick in past some threshold n0, an algorithm that is Theta(n log n) can genuinely lose to a Theta(n^2) one on small inputs, where the hidden constants and the low-order terms dominate. This is not a flaw in the notation — it is exactly what the asymptotic viewpoint chooses to ignore, and it is why real libraries often switch to insertion sort for tiny subarrays even though it is asymptotically worse.
Third, a missing Theta is information too. If the best ceiling you can prove is O(n^2) but the best floor you can prove is Omega(n), you have not failed — you have honestly located a gap, and closing it (by sharpening one side until they meet) is often where the real algorithmic insight lives. Resist the temptation to quietly write Theta(n^2) just because the O is n^2; a Theta claim asserts the floor too, and you must actually have it.