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