Asymptotic Notation: A Complete Guide to O, Ω, and Θ

Why Exact Step Counts Are Not the Right Tool

Analyzing an algorithm by counting its exact number of primitive operations, as discussed earlier in this series regarding insertion sort, produces expressions that are precise but unwieldy, and that depend on implementation details, such as programming language and hardware, that have nothing to do with the algorithm's fundamental efficiency. Asymptotic Notation solves this by describing how an algorithm's running time grows as the input size becomes arbitrarily large, ignoring constant factors and lower-order terms that become insignificant at scale.

Big-O Notation: An Asymptotic Upper Bound

O-notation (read "Big-O") describes an asymptotic upper bound on a function's growth rate. Formally, for a function f(n), we write f(n) = O(g(n)) if there exist positive constants c and n₀ such that:

0 ≤ f(n) ≤ c · g(n)  for all n ≥ n₀

In plain language, this means that beyond some point n₀, the function f(n) never exceeds a constant multiple of g(n). Big-O gives an upper bound, so saying an algorithm runs in O(n²) time means it never takes asymptotically more than quadratic time, though it might take less.

As a worked example, consider proving that f(n) = 3n² + 2n + 5 is O(n²). We need to find constants c and n₀ satisfying the definition.

3n² + 2n + 5 ≤ 3n² + 2n² + 5n²  (for n ≥ 1, since n ≤ n² and 1 ≤ n²)
             = 10n²

So choosing c = 10 and n₀ = 1 satisfies:
3n² + 2n + 5 ≤ 10n²  for all n ≥ 1

Therefore, 3n² + 2n + 5 = O(n²)

Big-Omega Notation: An Asymptotic Lower Bound

Ω-notation (read "Big-Omega") describes an asymptotic lower bound, the mirror image of Big-O. We write f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that:

0 ≤ c · g(n) ≤ f(n)  for all n ≥ n₀

This means f(n) grows at least as fast as a constant multiple of g(n) beyond some point. Saying an algorithm runs in Ω(n log n) time means it always takes at least that much time asymptotically, no matter how cleverly it is implemented — this is often used to establish fundamental lower bounds on entire classes of algorithms, such as the proof that comparison-based sorting requires at least Ω(n log n) comparisons in the worst case.

Big-Theta Notation: A Tight Asymptotic Bound

Θ-notation (read "Big-Theta") describes a tight bound: a function that is both O(g(n)) and Ω(g(n)) simultaneously. Formally, f(n) = Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that:

0 ≤ c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)  for all n ≥ n₀

This means f(n) is sandwiched between two constant multiples of g(n) for sufficiently large n. Theta notation gives the most precise asymptotic characterization: saying an algorithm's running time is Θ(n²) means it grows exactly proportionally to n², neither faster nor slower asymptotically.

An important theorem connects all three notations: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). This means proving a tight bound can always be done by separately establishing an upper bound and a lower bound.

A Practical Comparison of the Three Notations

O(g(n))  — "grows no faster than g(n)"     — upper bound
Ω(g(n))  — "grows at least as fast as g(n)" — lower bound
Θ(g(n))  — "grows exactly at the rate of g(n)" — tight bound

Example with f(n) = 3n² + 2n + 5:
f(n) = O(n³)   — true, but not tight (n³ grows faster)
f(n) = O(n²)   — true and tight
f(n) = Θ(n²)   — true, the precise characterization
f(n) = Ω(n)    — true, but not tight
f(n) = Ω(n²)   — true and tight

Additional Related Notations: o and ω

Two further notations express strict, non-tight bounds. o-notation (little-o) describes an upper bound that is not asymptotically tight: f(n) = o(g(n)) means f(n) becomes insignificant compared to g(n) as n grows, formally that for every positive constant c, there exists an n₀ such that f(n) < c · g(n) for all n ≥ n₀. Similarly, ω-notation (little-omega) describes a strict lower bound. These are used less frequently than O, Ω, and Θ but are occasionally useful for precisely comparing growth rates that differ in a fundamental way.

Common Growth Rates, From Fastest to Slowest

Algorithm running times fall into a small number of common growth rate categories, which every programmer should be able to recognize and order by relative speed for large inputs.

Ordered from fastest-growing (worst) to slowest-growing (best):

O(n!)        factorial      — brute-force permutation problems
O(2ⁿ)        exponential    — exhaustive search over subsets
O(n³)        cubic          — naive matrix multiplication
O(n²)        quadratic      — insertion sort, bubble sort
O(n log n)   linearithmic   — merge sort, heapsort, efficient sorting
O(n)         linear         — single pass through the input
O(log n)     logarithmic    — binary search
O(1)         constant       — hash table lookup (average case)

A crucial intuition to internalize is how dramatically these rates diverge as n grows. For an input of size one million, an O(n) algorithm performs roughly a million operations, while an O(n²) algorithm performs roughly one trillion operations — a difference that transforms a task from instantaneous to practically impossible on the same hardware.

Properties That Make Asymptotic Notation Useful for Proofs

Asymptotic notation follows several useful mathematical properties that simplify analysis.

• Transitivity: if f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)). This holds for Ω and Θ as well.
• Reflexivity: f(n) = O(f(n)), and similarly for Ω and Θ.
• Symmetry: f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)). Note that this symmetry does not hold for O and Ω individually.
• Transpose Symmetry: f(n) = O(g(n)) if and only if g(n) = Ω(f(n)), formalizing the intuitive relationship that O and Ω are mirror images of each other.

Why Mastering This Notation Is Essential

Every algorithm analyzed throughout the remainder of this series will be described using these notations, almost always Θ when a tight characterization is known, or O when only an upper bound has been established. Fluency with these definitions — being able to both interpret a stated bound and prove one directly from the formal definition when needed — is a prerequisite for understanding, comparing, and eventually designing efficient algorithms.