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

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

This saids: there exists a constant $M \geq 0$ and a constant $δ > 0$ , as $x \in (a - δ, a) \cup (a, a + δ)$ , $\frac{f ( x )}{g ( x )} \leq M$ , or

∣ f (x) ∣ \leq M ∣ g (x) ∣

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

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

\frac{f ( n )}{n ^{2}} = 3 + \frac{5}{n} + \frac{2}{n ^{2}}

as $N \geq 1$ , $\frac{f ( n )}{n ^{2}} \leq 3 + 5 + 2 = 10$ , which saids $∣ f (n) ∣ \leq 10∣ n^{2} ∣$ , it’s bounded by $n^{2}$

Big Theta Notation: Same Growth Rate

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

0 < c_{1} \leq \frac{f ( n )}{g ( n )} \leq c_{2}

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

\frac{f ( n )}{g ( n )} \geq c_{1} > 0

little $o$ : strict ceiling

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

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

symbol	Asymptotic meaning	read it out	The algorithm is…
$f (x) ≺ 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) = Ω (g (x))$	$f (x)$ grows at least as fast as $g (x)$	omega of g of x
$f (x) ≻ g (x)$	$f (x) = ω (g (x))$	$f (x)$ grows strictly faster than $g (x)$	little omega of g of x
$f (x) ≍ g (x)$	$f (x) = Θ (g (x))$	$f (x)$ grows as fast as $g (x)$	theta of g of x