Why does the Big Oh (and similar) notations needs $n_0$?

88 Views Asked by At

The generally agreed definition of the Big Oh notation (afaik) is as follows:

The function $f(n)$ is $O(g(n))$ if there exists constants $c$ and $n_0$ such that for all $n \ge n_0$, $f(n) \le c g(n)$.

Why can't we replace $n_0$ by a constant value, say, $1$? In this case, I can define $c'$ to be: $\max\left(c, \max_{1 \le i \le n}\frac{f(i)}{g(i)} \right)$, and the inequality should hold, right?

2

There are 2 best solutions below

7
On

if $g(1)=0$ you get issues. It's simply more convenient to ignore small $n.$

0
On

Suppose you have 2 algorithms, with runtimes

$$f_A(x) = 2^x~\log(x) \tag{A}$$ $$f_B(x) = x^2 \tag{B}$$

Which one should be designated as slower? Hopefully it is intuitive that the exponentially growing algorithm is slower. But $f_A(1) = 0$ , whereas $f_B(1) = 1$. In fact, depending on the base chosen for the logarithm, even large values of $x$ could have $f_A(x) < f_B(x)$. So it is better to say "eventually $f_A$ becomes larger than $f_B$, rather than "always $f_A$ is larger than $f_B$".