# Why should small o notation has to satisfy the equation for all values of the constant

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 ?

• 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?
– D.W.
Jun 9 '16 at 18:00
• 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? Jun 9 '16 at 18:02
• 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!)
– D.W.
Jun 9 '16 at 18:09

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.

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