Big Omega notation

Big Omega notation ( $Ω$ ) gives an asymptotic lower bound on a function’s growth. Writing $f (n) = Ω (g (n))$ means: for large enough $n$ , $f (n)$ is at least a constant times $g (n)$ . It’s the dual of Big O notation — Big O is “no faster than,” Big Omega is “no slower than.”

Formally:

$f (n) = Ω (g (n)) ⟺ \exists c > 0, n_{0} > 0 : \forall n \geq n_{0}, f (n) \geq c \cdot g (n) .$

Pick a positive constant $c$ and a threshold $n_{0}$ . For all inputs bigger than $n_{0}$ , $f$ is bounded below by $c \cdot g$ . Many pairs $(c, n_{0})$ work.

Why we need it

Big O alone doesn’t tell the full story. Saying $f (n) = O (n^{2})$ says $f$ grows no faster than $n^{2}$ — but $f$ could grow as slowly as constant time and the statement would still be true. Big Omega closes that gap: $f (n) = Ω (n)$ says $f$ grows at least as fast as $n$ .

The two together pin down a function’s growth rate. If $f (n) = O (n^{2})$ and $f (n) = Ω (n^{2})$ , then $f$ grows exactly like $n^{2}$ — i.e., $f (n) = Θ (n^{2})$ , the tight bound.

Worked example

Show that $f (n) = 8 n^{2} + 3 n + 5$ is $Ω (n^{2})$ .

We need $c > 0$ and $n_{0} > 0$ such that $8 n^{2} + 3 n + 5 \geq c \cdot n^{2}$ for all $n \geq n_{0}$ .

Try $c = 8$ . We need $8 n^{2} + 3 n + 5 \geq 8 n^{2}$ , i.e. $3 n + 5 \geq 0$ , which holds for all $n \geq 0$ . So $c = 8, n_{0} = 1$ works.

Therefore $f (n) = Ω (n^{2})$ .

Where Big Omega is used

The most common use of Big Omega is to argue lower bounds for problem complexity — not for specific algorithms but for all possible algorithms solving the problem.

Example statements:

“Comparison-based sorting requires $Ω (n lo g n)$ comparisons.” This says no comparison sort can do better than $n lo g n$ in the worst case — proven by an information-theoretic argument over the decision tree of comparisons.
“Searching an unsorted array requires $Ω (n)$ comparisons in the worst case.” Any search must look at every element in the worst case where the target is at the end (or absent).
“Multiplying two $n$ -bit integers takes $Ω (n)$ time.” You at least have to read the inputs.

These are fundamental limits. No clever algorithm can beat them; the matching upper bound (heap sort, linear scan, schoolbook multiplication) shows the limits are tight.

Common misuse

Big Omega is sometimes informally used to mean “at least this fast” in the running time sense — e.g., “this algorithm is $Ω (n^{2})$ ” intended to mean “in the worst case it actually takes $n^{2}$ time.” That’s a sloppy way of saying $Θ (n^{2})$ .

The clean usage:

$T (n) = O (g (n))$ : an upper bound on the algorithm’s worst-case time.
$T (n) = Ω (g (n))$ : a lower bound on the algorithm’s worst-case time. Less commonly used.
$T (n) = Θ (g (n))$ : both, i.e. a tight characterisation.

For most practical algorithm analysis, Big O is what gets reported, often informally meant as Big Theta. Big Omega gets explicit attention mainly when proving lower bounds on problems.

Properties

Many of the Big O properties have $Ω$ duals.

Sum: if $f_{1} = Ω (g_{1})$ and $f_{2} = Ω (g_{2})$ , then $f_{1} + f_{2} = Ω (max (g_{1}, g_{2}))$ .
Polynomials: $a_{k} n^{k} + a_{k - 1} n^{k - 1} + \dots = Ω (n^{k})$ when $a_{k} > 0$ . The leading term dominates from below as well.
Symmetric duality: $f (n) = O (g (n))$ if and only if $g (n) = Ω (f (n))$ . Saying ” $n$ grows no faster than $n^{2}$ ” is the same as saying ” $n^{2}$ grows no slower than $n$ .”

Best-case vs worst-case vs Big Omega

A common confusion: Big Omega is not the same as best-case running time.

“Best-case running time of binary search is $Θ (1)$ ” — a statement about a specific input (the target is at the middle).
“Binary search runs in $Ω (lo g n)$ in the worst case” — a lower bound on the worst-case time.

Big O / Omega / Theta are about the asymptotic growth of whichever function you’ve chosen to study — best-case time, worst-case time, average-case time, all amenable. The notation describes how the function scales, not which function you’ve picked.

In context

Big Omega is one of the three asymptotic-bound notations:

Big O notation ( $O$ ) — upper bound. The most-used.
Big Omega ( $Ω$ ) — lower bound. Mostly used for problem-complexity arguments.
Big Theta notation ( $Θ$ ) — tight bound. Combines both.

These describe growth rates of functions; for the analysis of running times of specific algorithms see Algorithm analysis.

Idriss Rami — Notes

Explorer