What does it mean by "f is dominated by g asymptotically" for f(n)=o(g(n))?

Question

I'm having a real hard time wrapping my head around these definitions. I can't seem to understand them. Could someone please explain in simpler terms, or direct me to a resource that could help?

Also its not just small o that I'm having trouble with its all of them. I can't seem to get the concept

ex.

f(n)= Ω(g(n)) means f is bounded below by g asymptotically.

Thanks!

Answer 1

Let $f$ and $g$ be two functions.

We say that $f(n) = o(g(n))$ if $\dfrac{f(n)}{g(n)}\rightarrow 0$ as $n\to +\infty$. Which basically means that $f$ is small in front of $g$ for high values of $n$.

We say that $f(n) = \omega(g(n))$ if $g(n) = o(f(n))$.

We say that $f(n) = O(g(n))$ if $f$ is bounded above by $g$, which means that $f$ is the same order of magnitude as $g$ or smaller. Formally, $f(n) = O(g(n))$ if you can find $M>0$ such that $|f(n)|\le M\cdot g(n)$ for $n$ big enough.

We say that $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $g(n) = O(f(n))$ which means that $f$ and $g$ are of the same order of magnitude for $n$ big enough.

We say that $f(n) \sim g(n)$ if $\dfrac{f(n)}{g(n)}\rightarrow 1$ as $n\to +\infty$. Which means that $f$ and $g$ are equivalent asymptotically.

We say that $f(n) = \Omega(g(n))$ if $f(n)$ is bounded below by $g$, so that there exists $M>0$ such that for $n$ big enough, $|f(n)| > M\cdot g(n)$.

Answer 2

$f(n)= \mathcal{o}(g(n))$ as $n\to\infty$ simply means that there exists a natural number $N\in\mathbb{N}$ beyond which ($\forall n>N$) you can write this equality:

$f(n)=\alpha(n)\cdot g(n)$

with $\alpha (n)$ a function infinitesimal as $n\to\infty$:

$$\lim_{n\to\infty}\alpha(n)=0$$