# Asymptotic Analysis

**Date:** 2020-01-17

#### BIG - OH

Basically, if O(g(n)) = f(n), then g(n) is the **upper bound/ceiling} of f(n)**. This also means that f(n) cannot have a complexity **greater** than g(n).

**Limit Definition of Big-Oh**
$$
\lim_{n \to \infty } \frac{f(n)}{g(n)}\neq\infty \Rightarrow f(n) \in O(g(n))
$$

#### BIG OMEGA

If f(n) = $\Omega(g(n))$, then g(n) is the **lower bound/floor** of f(n). Or f(n) cannot have a complexity lesser} than g(n).

**Limit Definition of Big Omega**
$$
\lim_{n \to \infty }\frac{f(n)}{g(n)}\neq0\Rightarrow \in\Omega(g(n))
$$

#### BIG THETA

When f(n) = $\Theta(g(n))$, then f(n) has a complexity exactly g(n). $\Theta $ is the intersection of O and $\Omega$

**Limit Definition of Big Theta**
$$
0<\lim_{n \to \infty }\frac{f(n)}{g(n)}<\infty \Rightarrow f(n)\in\Theta (g(n))
$$

**Note:** the equal sign means existence/membership instead of equality.

**Prove:** $3n^{2} + 4 = O(n^{2})$
$$
3n^{2} + 4 \leq cn^{2}
$$
**Explanation:** Find c and $n_{0}$ where $\forall n \leq n_{0}$. There are infinitely many pairs of c and $n_{0}$ and one example is enough to prove the function. Such as when c = 4 and $n_{0} = 2$. The inequality will always be true for that pair.
$$
\begin{align*}
3n^{2}+4\leq 4n^{2}\\
\frac{4}{n^{2}}\leq 4-3\\
\frac{1}{n^{2}}\leq \frac{1}{4}
\end{align*}
$$

**Prove:** $3n^{2} - 4 \neq O(n)$
$$
\begin{align*}
3n^{2} - 4 \leq cn \\
3n - \frac{4}{n} \leq c
\end{align*}
$$
**Explanation:** The inequality will reach a contradiction for sufficiently large values of n since c remains a constant. Since it is a linear function as n gets significantly larger it will obviously greater than a constant c.

#### little-oh

When f(n)'s complexity is less than g(n).

**Limit Definition of little-oh**
$$
\lim_{n \to \infty }\frac{f(n)}{g(n)}=0\Rightarrow f(n)\in o(g(n))
$$

#### little-omega

When f(n)'s complexity is greater than g(n).

**Limit Definition of little-omega**
$$
\lim_{n \to \infty }\frac{f(n)}{g(n)}=\infty \Rightarrow f(n)\in \omega(g(n))
$$

***

### **Things to ponder about:**

1. If f(n) = o(g(n)), is g(n) = $\omega(f(n))$?

**Answer:** Basically, if $f(n) < g(n)$, is $g(n) > f(n)$. Obviously, that statement is true.

**Proof:** that $f(n) = o(g(n))$

2. If f(n) = $\omega(g(n))$, is f(n) + g(n) = $\Theta (f(n))$

**Answer:** When adding two functions, the resulting function is the more complex function(the function that dominates over the other). In this case, since $f(n) > g(n)$, therefore the resulting summation is f(n) = $\Theta (f(n))$. This makes the statement true.