Big-O's Cousins: Big-Omega and Big-Theta, and Why Worst-Case Isn't the Whole Story
Big-O only promises an upper bound on how bad things get — Big-Omega and Big-Theta describe the best case and the tight, honest middle.
Think about estimating a daily commute. Telling a coworker "worst case, it takes 45 minutes" gives them an upper bound — a guarantee it won't take longer than that, even though most days are faster. That single number, on its own, doesn't tell them whether the trip usually takes 10 minutes or 40. Big-O notation is exactly that kind of promise: an upper bound on how an algorithm's running time grows, and nothing more.
Big-Omega is the mirror image — a lower bound, "best case, it never takes less than X." An algorithm's Big-Omega describes how fast it can possibly run, the same way "even with zero traffic, the drive itself is at least 15 minutes" gives your coworker a floor they can count on regardless of how good their luck is.
Big-Theta is what you get when the upper and lower bounds actually meet — a tight bound saying the algorithm always runs within the same growth rate, both above and below, not just "no worse than this." If you can honestly say "this drive reliably takes between 30 and 40 minutes, no more and no less," that tight bracket is a Big-Theta bound, and it tells your coworker far more than either the worst-case or best-case number alone.
Big-O gets used almost exclusively in casual conversation about algorithms because a guaranteed worst case is usually the number engineers care about most — the promise that matters when a system has to handle its worst day, not its best one. But describing an algorithm only by its worst case can hide a lot of nuance about how it actually behaves the rest of the time.
Binary search shows all three at once: its worst case is O(log n), its best case — the lucky search that finds the target on the first comparison — is Omega(1), and because those two cases genuinely differ, binary search's tight bound is written as Theta(log n) only when discussing its typical, guaranteed behavior across the full range of inputs, not the lucky first-try case. Knowing which of the three a claim is actually making is the difference between reading a performance claim correctly and only getting half the picture.