# Algorithm - Growth of Functions
> There are big-O, big-Omega, big-Theta, little-o and little-omega in this page QQ

# 1. Big-O
:::info
Defnition:
$$
O(g(n))=\{f(n)|\exists c, n_0, s.t. 0\le f(n)\le cg(n)\forall n\ge n_0\}
$$
> in human language, the alien's language above means:
>
> if $f(n)=O(g(n))$
there exists $c$ and $n_0$ such that
$0\le f(n)\le cg(n)$
for all $n\ge n_0$

:::

for example:
# 2. Big-Omega
:::info
Defnition:
$$
\Omega(g(n))=\{f(n)|\exists c, n_0, s.t. 0\le cg(n)\le f(n)\forall n\ge n_0\}
$$
> if $f(n)=\Omega(g(n))$
there exists $c$ and $n_0$ such that
$0\le cg(n)\le f(n)$
for all $n\ge n_0$

:::
Same as Big-O, I'll give you a human version, but I think you can get it by observing the different.

# 3. Big-Theta
:::info
Defnition:
$$
\Theta(g(n))=\{f(n)|\exists c_1, c_2, n_0, s.t. 0\le c_1g(n)\le f(n)\le c_2g(n)\forall n\ge n_0\}
$$
> if $f(n)=\Theta(g(n))$
there exists $c_1$, $c_2$ and $n_0$ such that
$0\le c_1g(n)\le f(n)\le c_2g(n)$
for all $n\ge n_0$

:::


## Theorem 1: $f(n)=O(g(n))=\Omega(g(n))\iff f(n)=\Theta(g(n))$
Here is way you can understand it, it just the combination of big-O and big Omega. If $f(n)=O(g(n))=\Omega(g(n))$, $f(n)=\Theta(g(n))$, here is the proof:

Since $f(n)=\Omega(g(n))\rightarrow\exists c_1, n_1 s.t.0\le c_1g(n)\le f(n) \forall n\ge n_1$
and $f(n)=O(g(n))\rightarrow\exists c_2, n_2 s.t.0\le f(n)\le c_2g(n)\forall n\ge n_2$
there must exist a $n_3$ less or equall to both $n_1$ and $n_2$

$\exists c_1, c_2, n_3 s.t.0\le c_1g(n)\le f(n)\le c_2g(n)\forall n\ge n_3\rightarrow f(n)=\Theta(g(n))$

## Theorem 2: $lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=a, a\neq 0$
Fun fact, $lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=a$, if $f(n)=\Theta(g(n))$, check the definition, then you will know how it work.

> $\lim_{n \to \infty} h(n) = L$, if and only if for all $c > 0$, there exists an $n_0 > 0$ such that for all $n > n_0$, $|h(n) - L| < c$
## Theorem 3: $f(n)=\Theta(g(n))\iff g(n)=\Theta(f(n))$
Also, if $f(n)=\Theta(g(n))$, $g(n)=\Theta(f(n))$, here is why:

$f(n)=\Theta(g(n))\rightarrow\exists c_1, c_2, n_0, s.t. 0\le c_1g(n)\le f(n)\le c_2g(n)\forall n\ge n_0\rightarrow$
$\exists \frac{1}{c_1}\space s.t.\space 0\le g(n)\le \frac{1}{c_1}f(n) \space \forall n\ge n_0$ and $\exists \frac{1}{c_2}\space s.t.\space 0\le \frac{1}{c_2}f(n)\le g(n) \space \forall n\ge n_0 \rightarrow$
$\exists \frac{1}{c_1}, \frac{1}{c_2}, n_0, \space s.t.\space 0\le \frac{1}{c_2}f(n)\le g(n)\le \frac{1}{c_1}f(n)\space \forall n\ge n_0\rightarrow$
$g(n)=\Theta(f(n))$

# 4. Little-o
:::info
Defnition:
$$
o(g(n))=\{f(n)|\forall c,\exists n_0 \space s.t. 0\le f(n)\le cg(n)\forall n\ge n_0\}
$$
> If $f(n)=o(g(n))$, for all constant $c$, there exists a $n_0$, such that $0\le f(n)\le cg(n)$ for all $n\ge n_0$

:::

the big different between big-O and Little-O is about the constant $c$, for example:
$n^2=O(2n^2)$, $\exists n_0 \space s.t. 0\le f(n)\le cg(n)\forall n\ge n_0$ makes sence when $c\ge\frac{1}{2}$, it ; However when it comes to little o, something went wrong since c has to be any number.

## Theorem 4: $f(n)=o(g(n))\iff lim_{n\leftarrow\infty}\frac{f(n)}{g(n)}=0$
I'm just gonna proof one side:

$\lim_{n \to \infty} h(n) = L$, if and only if for all $c > 0$, there exists an $n_0 > 0$ such that for all $n > n_0$, $|h(n) - L| < c$

Let $h(n)=\frac{f(n)}{g(n)}$ and $L=0$
$|\frac{f(n)}{g(n)} - 0| < c \rightarrow -c< \frac{f(n)}{g(n)} < c \rightarrow -cg(n)< 0<f(n) < cg(n)$
$lim_{n\leftarrow\infty}\frac{f(n)}{g(n)}=0 \rightarrow f(n)=o(g(n))$
# 5. Little-omega
:::info
Defnition:
$$
\omega(g(n))=\{f(n)|\forall c,\exists n_0 \space s.t. 0\le cg(n)\le f(n)\forall n\ge n_0\}
$$
> If $f(n)=\omega(g(n))$, for all constant $c$, there exists a $n_0$, such that $0\le cg(n)\le f(n)$ for all $n\ge n_0$

:::

## Theorem 5: $f(n)=\omega(g(n))\iff lim_{n\leftarrow\infty}\frac{f(n)}{g(n)}=\infty$
Let's prove the equivalence:

$$
f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty
\quad \text{(assuming } f(n), g(n) > 0 \text{ for large } n\text{)}
$$

---
If $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

Then, for all constant $c > 0$, there exists $n_0$ such that for all $n > n_0$,

$$
\frac{f(n)}{g(n)} > c \Rightarrow f(n) > c \cdot g(n)
$$

Therefore, $f(n) = \omega(g(n))$.

---

If $f(n) = \omega(g(n))
\Rightarrow \forall c > 0, \exists n_0 : f(n) > c \cdot g(n) \text{ for all } n > n_0$

Fix any number $M > 0$. Then $1, 2, \dots, M$ are all constants.

Since $f(n) = \omega(g(n))$, we know that for each such $c$, eventually:

$$
\frac{f(n)}{g(n)} > M
$$

Therefore, $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

# Features between them
## Transitivity
All of them have transitivity, for example:
$$
f(n)=O(g(n)) \text{ and } g(n)=O(h(n))\rightarrow f(n)=O(h(n))
$$
## Reflexivity
All the big guys have reflexivity.
* $f(n)=O(f(n))$
* $f(n)=\Omega(f(n))$
* $f(n)=\Theta(f(n))$
## Symmetry
which is the theorem 3:
$$
f(n)=\Theta(g(n))\leftrightarrow g(n)=\Theta(f(n))
$$
## Transpose symmetry
1. $f(n)=O(g(n))\iff g(n)=\Omega f(n)$
2. $f(n)=o(g(n))\iff g(n)=\omega f(n)$

proof below:

### $f(n)=O(g(n))\iff g(n)=\Omega f(n)$

$f(n) = O(g(n))$ means:
$$
\exists c, n_0, s.t. 0\le f(n)\le cg(n)\space\forall n\ge n_0
$$

From that, we can write $g(n) \ge \frac{1}{c} f(n)\space\forall n \ge n_0$
which satisfies the definition of $g(n) = \Omega(f(n))$

---
$f(n) = \Omega(g(n))$ means:
$$
\exists c, n_0, s.t. 0\le cg(n)\le f(n)\space\forall n\ge n_0
$$

From that, we can write $0\le g(n) \le \frac{1}{c} f(n)\space\forall n \ge n_0$
which satisfies the definition of $g(n) = O(f(n))$

### $f(n)=o(g(n))\iff g(n)=\omega f(n)$

$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
\rightarrow \lim_{n \to \infty} \frac{g(n)}{f(n)} = \infty
\rightarrow g(n) = \omega(f(n))$
and
$\lim_{n \to \infty} \frac{g(n)}{f(n)} = \infty
\rightarrow \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
\rightarrow f(n) = o(g(n))$.

Therefore,
$$
f(n) = o(g(n)) \iff g(n) = \omega(f(n))
$$

# Reference
* https://medium.com/@kevintsai0808/%E6%BC%94%E7%AE%97%E6%B3%95-%E8%AA%B2%E7%A8%8B%E5%BF%83%E5%BE%97-%E4%BA%8C-6b07c6a63486

# some tips
To slow down the speed of prof. Tsai's or any others teaching, I've got some questions to ask. 😈
* :I cannot understand the the last slide, could you explained again? I cannot follow up(with a pitty face). I mean the whole page of it QQ
* :Can you give us some examples?
* :What is the biggest diffirent between XXX and OOO? Could you make a comparison?
* :Can you draw the algorithm down on the white board? I just cannot understand what you written on your ipad (to force him to use the white board)