1
$\begingroup$

Big-O of a function i.e. f(n) = O(g(n)) is such that both c and $\textbf{n}_0$ can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the following condition exists:

f(n) = o(g(n)) means for all c > 0 there exists some $\text{n}_0$ > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ $\text{n}_0$. The value of $\text{n}_0$ must not depend on n, but may depend on c.

But for the conditions,

for all c > 0

$\text{n}_0$ may depend on c

we can simply select the value of $\text{n}_0$, based on the value of c, so that the equation is satisfied. So why should it satisfy for all values of c ?

$\endgroup$
  • 2
    $\begingroup$ I don't understand what you are asking. Why does it need to hold for all values of $c$? Because that's the definition. What kind of answer are you looking for? What specifically has you confused? $\endgroup$ – D.W. Jun 9 '16 at 18:00
  • $\begingroup$ Exactly. Why does the little o's definition say for all values of c, while for big o, we can choose the value for c. Is there any specific reason? I mean even if it says for all values of c, we can choose n0 accordingly right. So why for all values of c > 0? $\endgroup$ – Kenpachi Jun 9 '16 at 18:02
  • 2
    $\begingroup$ Because it didn't say "for all $c$", it would be a difference concept? Because the current concept is useful? I'm not sure what kind of answer you're hoping for. Are you asking about the difference between "for all $c$" vs "for all $c>0$"? Here's a suggestion to improve your question. Edit your question to include a vision of an alternate universe: e.g., propose an alternate definition, and argue for why you think the alternate makes sense, and then ask why we didn't use that alternate. I think that'd provide something a bit more concrete to respond to. (And welcome to CS.SE, by the way!) $\endgroup$ – D.W. Jun 9 '16 at 18:09
1
$\begingroup$

Here's the intuition:

  • big-O ($O(\cdot)$) is sort of like an asymptotic version of "$\le$" (less than or equal)

  • little-O ($o(\cdot)$) is sort of like an asymptotic version of "$<$" (strictly less than)

Just like it is useful to have both $\le$ and $<$, it is useful to have asymptotic versions of those.


Now for the definition to actually behave like "an asymptotic version of $<$", we need it to be phrased the way it is.

For $f(n) = o(g(n))$ to hold, we want $f$ to grow asymptotically strictly slower than $g$. If there was some $c$ such that $f(n) \approx c \cdot g(n)$ for all $n$, then $f$ would be growing at asymptotically the same rate as $g$, so we wouldn't want $f(n) = o(g(n))$ to be true. That's why the definition is the way it is.


Why does the condition say "for all $c>0$" rather than "for all $c$"?

Well, when $c=-42$ (say), the condition $0 \le f(n) < c g(n)$ simply cannot hold. For the functions we consider in computer science, it is assumed that $f(n),g(n)$ are never negative. Now you can't have $f(n) < -42 \cdot g(n)$, since a positive number can't be less than a negative number.

So if we replaced "for all $c>0$" with "for all $c$", it'd be impossible to satisfy the conditions of the definition. We want, for instance, $n^2 = o(n^3)$ to be true... but if we changed the definition to use "for all $c$" instead of "for all $c>0$", it wouldn't be true. So we craft the conditions of the definition so they are attainable in at least some cases, to ensure the definition doesn't become degenerate and useless.

$\endgroup$
2
$\begingroup$

Consider this also (more?) common definition:

$\qquad\displaystyle f \in o(g) \quad\mathbin{:\!\!\iff}\quad \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

Do you see now why we need to get below all factors $c$ in your definition? If not, we would have $f \in \Omega(g)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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