Asymptotic Analysis

Asymptotic Notations Table

Notation	Approx.	Growth	Test
$f(n)=o(g(n))$	$<$	Strictly smaller than $g(n)$	${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=0$
$f(n)=O(g(n))$	$\le$	At most as large as $g(n)$	${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=0\text{ or }c$
$f(n)=\Omega (g(n))$	$\ge$	At least as large as $g(n)$	${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty \text{ or }c$
$f(n)=\omega (g(n))$	>$$\>	Strictly larger than $g(n)$	${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty$
$f(n)=\Theta (g(n))$	$\approx$	The same growth as $g(n)$	${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=c$

Properties of Asymptotic Notations

Transitivity

The following properties hold:

• $f(n)=\Theta ((g(n))\text{ and }g(n)=\Theta (h(n))⟹f(n)=\Theta (h(n))$
• $f(n)=O((g(n))\text{ and }g(n)=O(h(n))⟹f(n)=O(h(n))$
• $f(n)=\Omega ((g(n))\text{ and }g(n)=\Omega (h(n))⟹f(n)=\Omega (h(n))$
• $f(n)=o((g(n))\text{ and }g(n)=o(h(n))⟹f(n)=o(h(n))$
• $f(n)=\omega ((g(n))\text{ and }g(n)=\omega (h(n))⟹f(n)=\omega (h(n))$

Reflexivity

The following properties hold:

• $f(n)=\Theta (f(n))$
• $f(n)=O(f(n))$
• $f(n)=\Omega (f(n))$

Symmetry & Transpose Symmetry

The following properties hold:

• $f(n)=\Theta ((g(n))⟺g(n)=\Theta ((f(n))$.
• $f(n)=O((g(n))⟺g(n)=\Omega ((f(n))$.
• $f(n)=o((g(n))⟺g(n)=\omega ((f(n))$.

Proposition

Asymptotic notations are not linear ordering.

Proposition

$a(\log n{)}^k=o(n)$ for any positive constants $a>0$ and integer $k>0$.

Proof We can prove the following by repeatedly applying the L’Hopital’s rule: ${\lim }_{n\to \infty }\frac{a(\log n{)}^k}{n}=0$ $\square$