# Definition of an Upper Bound

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

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

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

• 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. – Dániel Somogyi Jun 3 '18 at 21:12
• 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. – Yuval Filmus Jun 3 '18 at 21:15
• 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. – Dániel Somogyi Jun 3 '18 at 21:23
• For historical reasons. People just copy the definition from the textbook. – Yuval Filmus Jun 3 '18 at 21:24
• 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! – Ahmed Kidwai Jun 4 '18 at 18:59