## ~

Given functions \(f(n)\) and \(g(n)\), if:

\begin{equation} \lim_{n\to \infty} \left(\frac{f(n)}{g(n)}\right) = 1 \end{equation}

we say that \(f \sim g\).

That – the relationship between \(f\) and \(g\) grows in a similar fashion as \(n\) increases. For instance:

- \(f(n) = n+1\)
- \(g(n) = n+2\)

Therefore:

\begin{equation} f\sim g = \lim_{n\to \infty} \frac{f(n)}{g(n)} = \lim_{n\to \infty} \frac{n+1}{n+2} = 1 \end{equation}

The \(\sim\) operator is *commutative* (\(f \sim g \Rightarrow g\sim f\)) and *transitive* (\(f\sim g, g\sim h \Rightarrow f \sim h\)).

## o(n)

Given two functions \(f(n)\), \(g(n)\), if their relationship shows:

\begin{equation} \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 \end{equation}

we can write it as

\begin{equation} f = o(g) \end{equation}

This tells us that if \(n\) becomes very large, \(g\) becomes much larger than \(f\). \(f\) does not grow nearly as fast as \(g\).

The operation is *not* commutative, but is *transitive* (\(f = o(g), g = o(h) \Rightarrow f = o(h)\))

## O(n)

Given two functions \(f(n)\), \(g(n)\).

\begin{equation} \lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty \end{equation}

that the relationship between \(f(n)\) and \(g(n)\) is countable as \(n\) trends to infinity.

We can also say that, given \(n\), \(n_0\), and some \(c\) which \(\forall n, n > n_0\), there is:

\begin{equation} |f(n)| < |cg(n)| \end{equation}

This tells us that \(f(n)\) does not grow much much faster than \(g(n)\).

Therefore:

- If \(f \sim g\), \(f = O(g)\) (as they grow together, \(f\) is not much faster)
- If \(f = o(g)\), \(f=O(g)\) (as \(f\) does not grow at all, \(f\) is not faster)

## \(\theta\)(n)

\(f=\theta(g)\) IFF \(f=O(g)\) and \(g=O(f)\), its essentially \(\sim\) but without the strict requirement of a 1:1 ratio.

## \(\omega\)(n) and \(\Omega\)(n)

The inverses of \(O\) and \(o\):

- \(f(n) = O(g(n)) \Rightarrow g(n) = \omega(f(n))\)
- \(f(n) = o(g(n)) \Rightarrow g(n) = \Omega(f(n))\)