1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – smiley Oct 25 at 7:52
  • $\begingroup$ 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. $\endgroup$ – Vimal Patel Oct 25 at 8:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.