What is the difference between Big(O) and small(o) notations in asymptotic analysis? [duplicate]

Question

What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ notaion for a bound that is also not tight? For example can I say that $5n=O(n^3)$?

I am also confused by what this statement in CLSR means "The main difference is that in $f(n) =O(g(n))$, the bound $0 \le f(n) \le cg(n)$ holds for some constant $c > 0$, but in $f(n) = o(g(n))$, the bound $0 \le f(n) < cg(n)$ holds for all constants $c > 0$." As the value of $c$ will differ in the inequality "$0 \le f(n)< cg(n)$ for all $n > n_0,c>0$. " for different $n_0$.

Answer 1

Bigoh notation $O$:

This is anlogous to $\le$. $f(n) = O(g(n))$ means that for large enough value of $n$ value of $f(n)$ will be within some constant factor of value of $g(n).$

Smalloh notation $o$:

This is anlogous to $<$ relation. Now, $f(n) = o(g(n))$ means that if you are given any constant $c>0$ you will be able to find out some constant $n_0>0$ such that for all $n\ge n_0$, $f(n) < c.g(n)$ holds.

Intuitively smalloh notation says that $f(n)$ is asymptotically slower than $g(n)$.

For example $3n = O(5n)$ but $3n\ne o(5n)$ because for latter case if I give you $c=1/5$ you will not able to find out value of $n_0$ such that for all $n\ge n_0, 3n < c.5n$.