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

Question

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 ?

Answer 1

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.

Answer 2

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