1
$\begingroup$

The definition my professor gave us is: f(n) is O(g(n) for constant c > 0 and n0 ≥ 0 where all n ≥ n0 and f(n) ≤ cg(n). I was wondering what n0 and n are?

Example:
for the function f(n) = an2+ bn + cn = (a+b+c)n2.
Assuming a,b,c were constants we can say: f(n) = O(n2) where f(n) ≤ cn2.

What am I actually looking and to make sure that n0 ≥ 0 where all n ≥ n0

$\endgroup$
2
$\begingroup$

Let me write the definition in a little bit more detail.

Suppose that $f(n),g(n)$ are two functions from $\mathbb{N}$ to $\mathbb{R}_+$, that is, they accept as input a natural number, and return as output a positive real number.

We say that $f(n) = O(g(n))$ if there exist $n_0 \in \mathbb{N}$ and $C \in \mathbb{R}_+$ such that for all $n \geq n_0$,

$$ f(n) \leq Cg(n). $$

In order to show that $f(n) = O(g(n))$, you have to find $n_0$ and $C$ such that for all $n \geq n_0$ it holds that $f(n) \leq Cg(n)$. You can choose whatever $n_0,C$ you want as long as the condition holds. It turns out that for this definition, we can always take $n_0 = 1$ (for other variants of the definition, this no longer holds). So you only have to find a positive constant $C > 0$ such that for all $n \geq 1$ it holds that $$ f(n) \leq Cg(n). $$ (This assumes that the first natural number is 1 rather than 0.)

Now we can answer your question:

  • $n$ is the argument of the functions $f,g$.
  • $n_0$ is the point beyond which the inequality $f(n) \leq C g(n)$ should hold. When proving that $f(n) = O(g(n))$, you get to choose $n_0$. In most cases you can just take $n_0 = 1$.

For the curious: why do we need $n_0$? Sometimes we would like to accommodate functions which are not strictly positive, but just eventually positive. For example, if 0 is a natural number (in contrast to the convention used above) then $n^2$ is not strictly positive, since it vanishes at $n = 0$. Therefore $n = O(n^2)$ is only true if we allow to "skip" $n = 0$, which we do by choosing $n_0 = 1$.

$\endgroup$
  • $\begingroup$ I don't totally agree with your 'for the curious' part. The $n_0$ is needed for the idea behind $\mathcal{O}$. If $f(n) \in{( \mathcal{O}(g(n))}$, then $g$ is growing at least as fast as $f$. So, from one point ($n_0$) $f(n) \leq{} Cg(n)$ must hold. But: it may be that$ f$ has a larger starting value. Simple example would be $f(n) = n² + 20$ vs. $g(n) = n³$. At the beginning ($n = 0$), $f$ is larger than $g$. But from one point $g$ 'outruns' $f$. And this will always happen, no matter how large the constant is, wich we add to $f$. It has nothing to do with positivity. $\endgroup$ – Dániel Somogyi Jun 3 '18 at 21:12
  • $\begingroup$ It turns out that if $g$ is always positive then $f(n) = O(g(n))$ iff there exists a constant $C>0$ such that $f(n) \leq Cg(n)$ for all natural $n$. Try it out in your example. $\endgroup$ – Yuval Filmus Jun 3 '18 at 21:15
  • $\begingroup$ Never thought about that (and never learned it). But why is $n_0$ not just fixed as $1$ then? It would take away one variable and simplify everything. $\endgroup$ – Dániel Somogyi Jun 3 '18 at 21:23
  • 1
    $\begingroup$ For historical reasons. People just copy the definition from the textbook. $\endgroup$ – Yuval Filmus Jun 3 '18 at 21:24
  • $\begingroup$ This is a great answer and I feel like I understand the subject matter now (can apply this to theta and omega now too). I honestly appreciate you for taking the time to answer. Thank you! $\endgroup$ – Ahmed Kidwai Jun 4 '18 at 18:59

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.