Asymptotic Notations Explained: Big O, Omega, and Theta

Big O is just one of three notations - here's how they all fit together.

Why Three Notations?

In the previous post, we learned that Big O notation describes the upper bound of an algorithm's complexity. But sometimes you want to say more than just "it's at most this slow." Sometimes you want to express a guarantee, a tight bound, or a lower bound.

That's where the three asymptotic notations come in:

Together, these give you a complete picture of an algorithm's behavior.

What "Asymptotic" Means

The word asymptotic comes from mathematics - it refers to the behavior of a function as the input approaches infinity. We're not interested in small inputs. When n = 5, almost any algorithm is fast. We care about what happens when n = 1,000,000 or n = 10^9. At those scales, the difference between O(n) and O(n²) is the difference between a millisecond and several hours.

Asymptotic analysis ignores:

• Machine-specific constants
• Low-order terms
• Coefficients

It captures only the essential growth rate that dominates at large n.

Big O - Upper Bound (Worst Case)

Formal definition: f(n) = O(g(n)) means there exist positive constants c and n₀ such that:

f(n) ≤ c × g(n) for all n ≥ n₀

In plain English: from some point onwards, g(n) (multiplied by a constant) is always at least as large as f(n).

Example f(n) = 3n + 5. We can show this is O(n):

• Choose c = 4, n₀ = 5
• For all n ≥ 5: 3n + 5 ≤ 4n ✓

Big O is the most commonly used notation because it answers the most practical question: "How bad can this get?"

Common mistake: Many people say "the time complexity is O(n²)" when they really mean "the exact time complexity is Θ(n²)." O(n²) just means "no worse than n²" - technically, an O(n) algorithm is also O(n²)! But in everyday usage, people usually mean the tightest O they can state.

Big Omega (Ω) - Lower Bound (Best Case)

Formal definition: f(n) = Ω(g(n)) means there exist positive constants c and n₀ such that:

f(n) ≥ c × g(n) for all n ≥ n₀

In plain English: from some point onwards, f(n) is always at least c × g(n). Omega gives you a floor - a guarantee that the algorithm will take at least this long.

Example: Sorting a list of n elements requires at least O(n log n) comparisons in the comparison-based model. This is a lower bound - no comparison-based sorting algorithm can do better. We write: Sorting complexity = Ω(n log n)

When is Ω useful? Omega is used in theoretical computer science to prove impossibility results - showing that no algorithm can solve a problem faster than a certain bound.

Big Theta (Θ) - Tight Bound (Exact Growth Rate)

Formal definition: f(n) = Θ(g(n)) if and only if:

f(n) = O(g(n)) AND f(n) = Ω(g(n))

In other words, f(n) and g(n) grow at the same rate (up to constant factors). Theta is the most precise notation - it pins down both the ceiling and the floor.

Example: Merge sort always performs Θ(n log n) operations - whether the input is sorted, reversed, or random. There's no best-case shortcut.

Contrast that with insertion sort:

• Best case (already sorted): Ω(n) - only one pass needed
• Worst case (reverse sorted): O(n²)
• So insertion sort is not Θ(n log n) - it doesn't have a tight bound that works for all inputs.

Visual Intuition

Imagine f(n) is a curve on a graph, and g(n) is a reference curve:

↑ | f(n)
  | /
  |/ O(g(n)) ----/-------- upper bound (ceiling)
  | / Θ(g(n)) / tight bound (matches both)
  | Ω(g(n)) ____________ lower bound (floor)
  +----------→ n

• O says: "f never goes above this ceiling (eventually)"
• Ω says: "f never goes below this floor (eventually)"
• Θ says: "f is sandwiched between the same ceiling and floor"

Little-o and Little-omega (Bonus Notations)

There are also strict versions of Big O and Omega:

Little-o (o(g(n))): f grows strictly slower than g. The difference is that Big O allows equality; little-o does not.

• Example: 2n = o(n²) but n² ≠ o(n²)

Little-omega (ω(g(n))): f grows strictly faster than g.

These are used less often in practice but appear in advanced algorithm analysis.

Comparing the Notations: A Summary

Practical Takeaways for Everyday Programming

• Use Big O when communicating worst-case performance (most common).
• Use Theta when you know the exact growth rate (e.g., merge sort is Θ(n log n)).
• Use Omega when you want to argue about what's impossible to improve.
• Always state which case (best/average/worst) your notation refers to, since the same algorithm can have different complexities in different scenarios.

Examples of All Three in One Algorithm

Linear search in an unsorted array looking for a target:

• Best case (target is first element): Ω(1) - found immediately.
• Worst case (target is last or not present): O(n) - scan the whole array.
• Average case (target is somewhere in the middle): Θ(n/2) = Θ(n).

So linear search is O(n), Ω(1), and its average case is Θ(n). It does not have a single tight-bound Θ that applies to all cases.

Summary

• Big O (O) - upper bound. The algorithm runs in at most this time. Most commonly used.
• Big Omega (Ω) - lower bound. The algorithm takes at least this long.
• Big Theta (Θ) - tight bound. The algorithm's runtime is exactly this growth rate (within constants).
• Asymptotic analysis focuses on large n, ignoring constants and lower-order terms.
• An algorithm can have different complexities for best, worst, and average cases.

Next up: we'll look at Best, Worst, and Average Case Analysis in depth - and why all three matter depending on your use case.