Asymptotic Notation: Big-O, Big-Ω, and Big-Θ

Big-O: Asymptotic Upper Bound

$f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that for all $n \ge n_0$:

$0 \le f(n) \le c \cdot g(n)$

In words: $f$ grows at most as fast as $g$, ignoring constant factors and small inputs. $O$ is pronounced “big-O”.

Big-$\Omega$: Asymptotic Lower Bound

$f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that for all $n \ge n_0$:

$0 \le c \cdot g(n) \le f(n)$

In words: $f$ grows at least as fast as $g$. The purple circles (worst-case cost) must be above the curve $c \cdot g(n)$.

Big-$\Theta$: Asymptotically Tight Bound

$f(n) = \Theta(g(n))$ iff $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. In words: $f$ and $g$ grow at the same rate, within constant factors.

Formal Definition

There exist $c_1, c_2 > 0$ and $n_0$ such that for all $n \ge n_0$:

$0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$

Examples

Function	Big-O	Big-$\Omega$	Big-$\Theta$
$3n^2 + 2n + 1$	$O(n^2)$ ✓, $O(n^3)$ ✓	$\Omega(n^2)$ ✓, $\Omega(n)$ ✓	$\Theta(n^2)$ ✓
$n \log n$	$O(n^2)$ ✓, $O(n \log n)$ ✓	$\Omega(n)$ ✓	$\Theta(n \log n)$ ✓
$n^2$	$O(n^2 \log n)$ ✓	$\Omega(n^2)$ ✓	Cannot say $n^2 = O(n \log n)$ ✗

Proving $3n^2 + 2n + 1 = O(n^2)$

We need $c$ and $n_0$ such that $3n^2 + 2n + 1 \le c \cdot n^2$ for all $n \ge n_0$.

For $n \ge 1$: $2n \le 2n^2$ and $1 \le n^2$, so $3n^2 + 2n + 1 \le 3n^2 + 2n^2 + n^2 = 6n^2$.

Choose $c = 6$, $n_0 = 1$. ✓

Common Growth Rates

Ranked from slowest to fastest:

$O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

The base of the logarithm is irrelevant: $\log_2 n$ and $\log_{10} n$ differ by a constant factor ($\log_2 n = \log_2 10 \cdot \log_{10} n$), which big-O absorbs.

Practical Interpretation

• $O(1)$: constant time, e.g. array access, arithmetic
• $O(\log n)$: binary search depth, divide-and-conquer recursion depth
• $O(n)$: single pass over all elements
• $O(n \log n)$: efficient comparison-based sorting
• $O(n^2)$: nested loops, insertion sort worst case
• $O(2^n)$: enumerating all subsets

$\Theta$, $O$, and $\Omega$ are Sets

Formally, $O(g(n))$ is a set of functions. Writing $f(n) = O(g(n))$ means $f(n) \in O(g(n))$. This set perspective makes the notation transitive: if $f \in O(g)$ and $g \in O(h)$, then $f \in O(h)$. Likewise for $\Theta$ and $\Omega$. In addition, $f \in \Theta(g)$ iff $g \in \Theta(f)$ (symmetry).

Summary

Notation	Meaning	Mnemonic
$O(g(n))$	Upper bound	”at most”
$\Omega(g(n))$	Lower bound	”at least”
$\Theta(g(n))$	Tight bound	”exactly” (within constants)
Rule of thumb	Drop constants and lower-order terms	$3n^2 + 4n \to O(n^2)$