$\Theta$ AND OTHER NOTATIONS

def: If $f(n) = O(g(n))$
then $g(n) = \Omega(f(n)).$

Thus, $O(f)$ contains all function with growth rate "equal or slower."

$\Omega(f)$ contains all function with growth rate "equal or faster."

def: If $f(n) = O(g(n))$ and $g(n)=O(f(n))$
then $f(n)=\Theta(g(n))$.

Equivalently, $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=c \in R^+$.

Thus,

$$\Theta(f)$ = $O(f) \cap \Omega(f)$$

In terms of growth rate,
$\Theta(f)$ contains functions growing at the same rate as $f$.

$O(f)$ contains function growing no faster than $f$

$\Omega(f)$ contains function at least as fast as $f$

def: (Small o and $\omega$ notations):

$f = o(g)$ if $\lim_{n \rightarrow \infty} f/g \rightarrow 0$

$f=\omega(g)$ if and only if $g \in o(f)$