Big-O vs. Big-Theta vs. Big-Omega

In everyday conversation, “Big-O” gets used as a catch-all for “how fast is this algorithm.” Formally, though, O, Ω, and Θ each answer a different question about an algorithm’s running time as a function of input size n:

• O (Big-O): an upper bound— “this algorithm never does more than roughly this much work.”
• Ω (Big-Omega): a lower bound— “this algorithm always does at least roughly this much work.”
• Θ (Big-Theta): a tight bound — both of the above at once, meaning the upper and lower bounds match.

Saying an algorithm is O(n²) means its running time grows no faster than some constant multiple of n², for large enough n. It says nothing about whether the algorithm might actually run faster on some or all inputs — only that n² is a ceiling.

This is why linear search is technically correct to describe as O(n²) — it never runs slower than that — even though O(n) is the far more useful and precise upper bound. In practice, people use O to mean the tightest known upper bound, which is why it gets used loosely in place of Θ.

Saying an algorithm is Ω(n) means its running time grows at least as fast assome constant multiple of n — a floor, not a ceiling. Every comparison-based sort, for instance, is Ω(n): you can’t sort a list without at least looking at every element once.

function findFirstEven(nums) {
  for (const n of nums) {
    if (n % 2 === 0) return n; // could return on the very first element
  }
  return null;
}
// Best case: Ω(1) — the first element might already be even
// Worst case: O(n) — might have to check every element

Notice this function has different bounds for its best and worst case — Ω describes the best case here, O describes the worst case, and neither alone tells the whole story.

Saying an algorithm is Θ(n log n) means its running time grows exactly proportionallyto n log n — the upper bound (O) and lower bound (Ω) coincide. This is the strongest, most informative statement you can make about an algorithm’s growth rate, because it rules out both “might be slower” and “might be faster.”

Merge sort is Θ(n log n): its best, average, and worst cases are all n log n, so the upper and lower bounds match exactly, in every case. Quicksort, by contrast, is only O(n²) and Ω(n log n) — its bounds don’t coincide, so it has no single Θ that covers every case; its average case, though, is Θ(n log n).

Searching an unsorted array of n elements for a target value, stopping as soon as it’s found:

• Best case — Ω(1): the target is the first element checked.
• Worst case — O(n): the target is last, or absent, and every element gets checked.
• No single Θ:because the best and worst cases differ, there’s no n-only tight bound covering the algorithm as a whole — only per-case statements.

Compare that to binary search, where even the worst case is O(log n) and the tight bound Θ(log n) applies uniformly because the halving behavior doesn’t depend on where the target happens to be.

In casual engineering conversation and even in most textbooks, “Big-O” is used as shorthand for “the tight growth rate” — what is formally Θ — because people almost always report the tightest bound they know, and an upper bound that’s also a lower bound is the most useful thing to say. Strictly, O only promises “no worse than,” but in practice, if someone says an algorithm “is O(n log n),” they usually mean it behaves like n log n, not merely that it’s bounded above by it.

• How to Analyze Time Complexity of Any Algorithm — the general method for deriving these bounds from code.
• Big-O Cheat Sheet — the common complexity classes these bounds are expressed in.
• Quicksort — a concrete example of an algorithm whose O and Ω bounds don’t coincide.
• Binary Search — an algorithm with a uniform Θ(log n) bound across best, average, and worst case reasoning.