Asymptotic Dominance

complexity-theory

Definition

Asymptotic Dominance

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

This is often written informally as

Common order

Common growth rates are ordered as follows:

where , , and .

Interpretation

If , then eventually grows faster than by more than any constant factor. In limit notation, this means

Thus means that logarithmic growth becomes negligible compared with linear growth, and means that every fixed polynomial is eventually dominated by an exponential function with base .