1
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ So the $n_0$ in the definitions are just for "convenience"? I mean, can I set $n_0$ to be any value as long as for all $n \ge n_0$, both $g(n)$ and $f(n)$ is well defined? $\endgroup$
    – Irvan
    Jul 23, 2015 at 5:57
  • 1
    $\begingroup$ if $g>0$ everywhere, you can take $n_0=0$ $\endgroup$
    – Mark Joshi
    Jul 23, 2015 at 6:01
  • $\begingroup$ Let $g$ to be the function such that: $g(i) = 1$ when $i \le 0$, and $g(i) = i$ otherwise. $\endgroup$
    – Irvan
    Jul 23, 2015 at 6:07
  • $\begingroup$ indeed if you modify $g$ to be positive, the problem goes away. Note, however that generally you don't want to change $g$ for $n$ large. The essential point is that $O$ notation is about big $n$ so just make the definition about big $n$ and don't waste time. $\endgroup$
    – Mark Joshi
    Jul 23, 2015 at 6:11
  • $\begingroup$ No no I mean, for that example, isn't $g(i)$ can be arbitrarily small (which now makes me realize that my $c'$ is wrong, as it can be arbitrarily large). Now it's looking like $n_0$ may be required but I'm interested in knowing what's the solid reasoning behind the addition of $n_0$, if any. $\endgroup$
    – Irvan
    Jul 23, 2015 at 6:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .