Asymptotic Notations

Big Three Ratio

Big $O$

Big $O$: The Ceiling

$f(n)=O(g(n))$ means $f(x)$ growth rate is upper-bounded by $g(x)$

$$\lim \_n\to \infty \frac{f(n)}{g(n)}<\infty$$

This saids: there exists a constant $M\ge 0$ and a constant $\delta >0$, as $x\in (a-\delta ,a)\cup (a,a+\delta )$, $\left|\frac{f(x)}{g(x)}\right|\le M$, or

$$|f(x)|\le M|g(x)|$$

, $f(x)$ is bounded by $g(x)$

Example 1

Prove that $f(n)=3n^2+5n+2=O(n^2)$

$$\left|\frac{f(n)}{n^2}\right|=\left|3+\frac{5}{n}+\frac{2}{n^2}\right|$$

as $N\ge 1$, $\left|\frac{f(n)}{n^2}\right|\le 3+5+2=10$, which saids $|f(n)|\le 10|n^2|$, it’s bounded by $n^2$

Big Theta Notation

Big Theta Notation: Same Growth Rate

$f(x)=\Theta (g(x))$ implies $f(x)$ has exactly the same growth rate as $g(x)$

$$0<c\_1\le \left|\frac{f(n)}{g(n)}\right|\le c\_2$$

Big Omega Notation

$f(x)=\Omega (g(x))$ saids that $\exists N>0$, as long as $n>N$

$$\left|\frac{f(n)}{g(n)}\right|\ge c\_1>0$$

Little $o$

little $o$: strict ceiling

$f(x)=o(g(x))$ means $f(x)$ becomes insignificant compared to $g(x)$

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

or $\lim \_n\to \infty \frac{o(g(n))}{g(n)}=0$

rules for little o:

• multiplying an constant doesn’t change its order: $Ao(f(x))=o(f(x))$
• multiplying an infinitesimal make it an even higher order infinitesimal:
  • $g(x)o(f(x))$ is $o(g(x)),o(f(x))$ or $o(f(x)g(x))$
• adding a higher order of infinitesimal doesn’t change its order: if $g(x)=o(f(x))$, then $o(f(x))+o(g(x))=o(f(x))$

Notations

symbol	Asymptotic meaning	read it out	The algorithm is…
$f(x)\prec g(x)$	$f(x)=o(g(x))$	$f(x)$ grows strictly slower than $g(x)$	little o of g of x
$f(x)⪯g(x)$	$f(x)=O(g(x))$	$f(x)$ grows no faster than $g(x)$	o of g of x
$f(x)⪰g(x)$	$f(x)=\Omega (g(x))$	$f(x)$ grows at least as fast as $g(x)$	omega of g of x
$f(x)\succ g(x)$	$f(x)=\omega (g(x))$	$f(x)$ grows strictly faster than $g(x)$	little omega of g of x
$f(x)\asymp g(x)$	$f(x)=\Theta (g(x))$	$f(x)$ grows as fast as $g(x)$	theta of g of x

Summary

• little means strict, big means no … than
• is “o” means upper-bound, is “omega” means lower-bound, is “theta” is the same order as