Asymptotic Analysis

Asymptotic Notations Table

Notation	Approx.	Growth	Test
		Strictly smaller than
		At most as large as
		At least as large as
		Strictly larger than
		The same growth as

Properties of Asymptotic Notations

Transitivity

The following properties hold:

Reflexivity

The following properties hold:

Symmetry & Transpose Symmetry

The following properties hold:

• .
• .
• .

Proposition

Asymptotic notations are not linear ordering.

Proposition

for any positive constants and integer .

Proof We can prove the following by repeatedly applying the L’Hopital’s rule: