# Asyptopic Notation

Asyptopic notation describes how algorithums running time grows with the size of its input.

## Big-O

Big-O describes the upper bound of the growth rate of a function. $f = O(g)$ means the function $f$ has a growth rate no larger than function $g$. The definition for Big-O is as follows, for functions $f, g : \mathbb{N} \rightarrow \mathbb{R}$, $f$ is $O(g)$ iff there is an $n_0 \in \mathbb{N}$ and $c > 0$ in $\mathbb{R}$ such that for all $n \geq n_0$: 

$$
0 \leq f(n) \leq cg(n)
$$ 

Asyptopic notation describes the long term behaviour of a function, thus $n_0$ allows us to discard the initial aytipical behavipur of the function. The constant $c$ is nessisary because multiplying a function by a constant doesnt change its growth rate. Even though for functions $f_1(n) = n$ and $f_2(n) = 2n$, $f_1(n) < f_2(n)$ for all $n > 0$, they still grow at a linear rate.


```python
import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(0, 10, 100)
f1 = [n for n in n]
f2 = [2*n for n in n]

plt.plot(n, f1)
plt.plot(n, f2)

plt.title('Growth rate of n vs 2n')
plt.show()
```

### Example

$$
3n^3 + 8 = O(n^3)
$$

To prove this, we need a $c$ and $n_0$ such that
$$
0 \leq 3n^3 + 8 \leq cn^3 \quad \text{for all $n_0 \geq n$}
$$

If we divide through by $n^3$ we get:
$$
3n^3 + 8 \leq cn^3 \iff 3 + \frac{8}{n^3} \leq c \quad \text{where $n > 0$}
$$

Now notice how $\frac{8}{n^3}$ is decreasing, and its maximum value is $8$, this tells us
$$
3 + \frac{8}{n^3} \leq 11 \quad \text{where $n > 0$}
$$

Thus $c = 11$ and $n = 1$, alternativly we could have picked $c = 4$ and $n = 2$


```python
import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(0, 2.5, 100)
f1 = lambda n: 3*n**3+8
f2 = lambda n: 11*n**3
f3 = lambda n: 4*n**3

plt.plot(n, [f3(n) for n in n], label="$4n^3$")
plt.plot(2, f3(2), marker='o', markersize=5)
plt.plot(n, [f2(n) for n in n], label="$11n^3$")
plt.plot(1, f2(1), marker='o', markersize=5)
plt.plot(n, [f1(n) for n in n], label="$3n^3 + 8$")

plt.title('Growth rate of $3n^3 + 8$ vs $11n^3$')
plt.legend()
plt.show()
```

## Laws of Big-O

The proof above is a proof by first principles, but their are some general laws which can make our proofs easier.

1. For any constant $a > 0$ in $\mathbb{R}$: $f = O(g) \implies a f = O(g)$
2. $f_1 = O(g_1)$ and $f_2 = O(g_2) \implies f_1 + f_2 = O(g_1 + g_2)$
3. $f_1 = O(g_1)$ and $f_2 = O(g_2) \implies f_1 f_2 = O(g_1 g_2)$
4. $f = O(g_1)$ and $g_1 = O(g_2) \implies f = O(g_2)$
5. For any $d \in \mathbb{N}$: if $f_1$ is a polynomial of degree $d$ with strictly positive leading coeffient then $f = O(n^d)$
6. For any constants $a > 0$ and $b > 1$: $n^a = O(b^n)$
7. For any constant $a > 0$ in $\mathbb{R}$: $ln(n^a) = O(lg(n))$
8. For any constants $a, b > 0$ in $\mathbb{R}$: $lg^a(n) = O(n^b)$

### Example

$$
\begin{align}
871n^3 + 13n^2 lg^5(n) + 18n + 566 &= 871n^3 + 13n^2 O(n) + 18n + 566 && \text{by Theorem 8} \\
&= 871n^3 + O(n^3) + 18n + 566 && \text{by Theorem 3}\\
&= (871n^3 + 18n + 566) + O(n^3)\\
&= O(n^3) + O(n^3)  && \text{by Theorem 5}\\
&= O(n^3)  && \text{by Theorem 2}\\
\end{align}
$$

## Big-$\Omega$

Big-$\Omega$ allows us to make statements about a lower bound such as "$f$ grows as least as fast as $g$". The definition is as follows: for functions $f, g: \mathbb{N} \rightarrow \mathbb{R}$, $f$ is $\Omega(g)$ is there is an $n_0 \in \mathbb{N}$ and $c > 0$ in $\mathbb{R}$ such that for all $n \geq n_0$:

$$
f(n) \geq cg(n) \geq 0
$$

## Laws of Big-$\Omega$

Just as with Big-O, we have simular laws for Big-$\Omega$.

1. For any constant $a > 0$ in $\mathbb{R}$: $f = \Omega(g) \implies af = \Omega(g)$
2. $f_1 = \Omega(g_1)$ and $f_2 = \Omega(g_2) \implies f_1 + f_2 = \Omega(g_1 + g_2)$
3. $f_1 = \Omega(g_1)$ and $f_2 = \Omega(g_2) \implies f_1 f_2 = \Omega(g_1 g_2)$
4. $f_1 = \Omega(g_1)$ and $g_1 = \Omega(g_2) \implies f_1 = \Omega(g_2)$
5. For any $d \in \mathbb{N}$: if $f$ is a polynomial of degree $d$ with strictly positive leading coefficient $f = \Omega(n^d)$
6. For any constant $a > 0$ in $\mathbb{R}$: $lg^a(n) = \Omega(lg(n))$

## Big-$\Theta$

Finnally Big-$\Theta$ defines a lower and upper bound, more formally if $f = O(g)$ and $f = \Omega(g)$ then $f = \Theta(g)$

1f17f203a9d1589a7a92180374e62088b5f80046
ipynb
Jupyter Notebook
Asymptotic Notation.ipynb
bens-notes/ads-notes
fdd273dd25e778551039a9f69740a8e1eaa641d8
MIT
Asymptotic Notation.ipynb
bens-notes/ads-notes
fdd273dd25e778551039a9f69740a8e1eaa641d8
MIT
Asymptotic Notation.ipynb
bens-notes/ads-notes
fdd273dd25e778551039a9f69740a8e1eaa641d8
MIT
Qwen/Qwen-72B
1. YES
2. YES