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

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$$.

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$$.

• Thnx.. I follow up question is that for those cases where it will be incorrect to use o (small oh) but correct to use O (big oh) for example 3n=O(5n) but 3n≠o(5n) will the value of $n_0$ be always equal to 1.Here I am obviously not considering the case where input size could be zero. – smiley Oct 25 '19 at 7:52
• In that particular case we can not find any value of $n_0$ for smalloh notation. But in case of bigohh notation any positive integer value will suffice for $n_0$. Does this address your doubt. – Vimal Patel Oct 25 '19 at 8:08