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:
| Notation | Symbol | Meaning | Describes |
|---|---|---|---|
| Big O | O | Upper bound | Worst case (at most) |
| Big Omega | Ω | Lower bound | Best case (at least) |
| Big Theta | Θ | Tight bound | Exact growth rate |
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
-
Osays: "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²)butn² ≠ 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
| Notation | Intuition | Analogy |
|---|---|---|
| O(g) | f ≤ c·g (eventually) | f ≤ g (≤) |
| Ω(g) | f ≥ c·g (eventually) | f ≥ g (≥) |
| Θ(g) | Both O and Ω hold | f = g (=) |
| o(g) | f/g → 0 as n→∞ | f < g (<) |
| ω(g) | g/f → 0 as n→∞ | f > g (>) |
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.
Top comments (0)