Landau Symbols

complexity-theory

Definition

Landau Symbols

Landau symbols are asymptotic notations used to compare the growth of functions while ignoring constant factors and finite initial behaviour.

For functions $f,g:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$, they describe whether $f$ is eventually bounded above by, bounded below by, tightly bounded by, or strictly smaller than $g$.

Symbols

Symbol	Name	Meaning
$O(g(n))$	Big-O notation	asymptotic upper bound
$\Omega (g(n))$	Big-Omega notation	asymptotic lower bound
$\Theta (g(n))$	Big-Theta notation	asymptotically tight bound
$o(g(n))$	small-o notation	strict asymptotic upper bound
$\omega (g(n))$	small-omega notation	strict asymptotic lower bound

Dominance

Definition

Asymptotic Dominance

Asymptotic dominance compares functions by their long-term growth. A function $g$ asymptotically dominates a function $f$ if $f$ grows strictly slower than $g$ as $n$ becomes large.

This is often written informally as

$$f(n)\ll g(n).$$

Link to original