Asymptotic Dominance

complexity-theory

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).$$

Common order

Common growth rates are ordered as follows:

$$1\ll \log n\ll \sqrt{n}\ll n\ll n\log n\ll n^{1+\epsilon }\ll n^2\ll n^3\ll n^k\ll c^n\ll n!\ll n^n,$$

where $c>1$, $k>3$, and $0<\epsilon <1$.

Interpretation

If $f(n)\ll g(n)$, then $g$ eventually grows faster than $f$ by more than any constant factor. In limit notation, this means

$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0.$$

Thus $\log n\ll n$ means that logarithmic growth becomes negligible compared with linear growth, and $n^k\ll c^n$ means that every fixed polynomial is eventually dominated by an exponential function with base $c>1$.