Asymptotic Notations — $O$, $\Omega$, $\Theta$

Asymptotic notation describes growth of $T(n)$ for large $n$, ignoring constants and lower-order terms.

1. Big O — Upper bound ($\le$)

$$O(g(n)) = \{ f(n): \exists c>0, n_0>0, 0 \le f(n) \le c\,g(n) \;\forall n \ge n_0 \}$$
Example: $3n^2+5n+2 = O(n^2)$ (choose $c=4$, $n_0=10$). Means algorithm at most that fast-growing.

2. Big Omega — Lower bound ($\ge$)

$$\Omega(g(n)) = \{ f(n): \exists c>0, n_0>0, 0 \le c\,g(n) \le f(n) \;\forall n \ge n_0 \}$$
Example: $n^2/2 - n = \Omega(n^2)$. Means algorithm at least that slow.

3. Big Theta — Tight bound ($=$)

$$\Theta(g(n)) = \{ f(n): \exists c_1,c_2>0, n_0>0, c_1 g(n) \le f(n) \le c_2 g(n) \;\forall n \ge n_0 \}$$
Equivalently $f(n)=\Theta(g(n)) \iff f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$.
Example: $3n^2+5n = \Theta(n^2)$.

Small o / small omega (strict)

• $o(g)$: $\forall c>0$ eventually $f(n) < c g(n)$ (non-tight upper).
• $\omega(g)$: strict lower.

Properties & Use

• Transitivity, reflexivity, symmetry ($\Theta$ symmetric).
• Transpose: $f=O(g) \iff g=\Omega(f)$.
• Used to classify algorithms: Linear search $O(n)$ worst, $\Omega(1)$ best, $\Theta(n)$ average; Merge sort $\Theta(n\log n)$; Binary search $\Theta(\log n)$.
• Hierarchy: $O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^2) \subset O(2^n)$.

Graphical intuition

Plot $c\cdot g(n)$ bounding $f(n)$ above ($O$), below ($\Omega$), or sandwiching ($\Theta$) beyond $n_0$.