Show that there exists a constant $c>0$ so that $f(n) \le cg(n)$ for every $n\ge 1$

Question

Given two positive functions $f(n)$,$g(n)$, such that $f(n)=O(g(n))$ (big O notation) show that there exists a constant $c>0$ so that $f(n)\le cg(n)$ for every $n\ge1$

I dont know how to solve this because I learned at class that $n$ can start start from any number.

For example if $g(n)=\log n$ it can't start from $n=1$ because $\log 1=0$

Answer 1

Let me repeat your sentence:

$f,g \geqslant 0$ and $f=O(g)$. Exist or not such $C>0$, that $f(n) \leqslant C \cdot g(n)$ for $\forall n \in \mathbb{N}$?

Answer is no, because big-O does not set restriction on some initial segment of $\mathbb{N}$. Let's define

$ f(n) = \left\{ \begin{array}{ll} 1 & \mbox{if } n = 1 \\ 0 & \mbox{if } n > 1 \end{array} \right. $

and let's take $g(n) = 0,\ \forall n \in \mathbb{N}$, then $f(n) \leqslant g(n)$ for $n > 1$.

Then, obviously, we have $f=O(g)$, but for any $C>0$ we have $1=f(1)>C \cdot g(1) = 0$.

Of course, if we consider $f>0$ functions, then, this contr example do not work and we can find $C>0$ for any $n$.

But also here we can make proof in less restrictions, then $f>0$. Let's call kernel of function set $ ker (f) = \left\lbrace n: f(n)=0 \right\rbrace = f^{-1}(0) $.

Now consider again $f,g \geqslant 0$ and $f=O(g)$. If $ker( f) = ker (g)$, then we can find $C>0$ such that for any $n$ $f(n) \leqslant C \cdot g(n)$ .

Answer 2

Let $f,g$ be positive and such that $f(n) = O(g(n))$ (as $n\to\infty$). By definition of $O(\cdot)$, there exists $N\geq 1$ and $C>0$ such that $f(n) \leq C\cdot g(n)$ for all $n \geq N$.

So how to deal with $1\leq n < N$? Well, you only have a finite number of them, so you can "incorporate that in the constant," separately. Set $$ C' \stackrel{\rm def}{=} \max\!\left(C, \frac{f(1)}{g(1)}, \frac{f(2)}{g(2)},\dots, \frac{f(N-1)}{g(N-1)}\right) $$ This is indeed a constant, positive. Moreover, for every $n\geq 1$:

• if $n \geq N$, then $f(n) \leq C\cdot g(n) \leq C' \cdot g(n)$, since $C' \geq C$.
• if $n < N$, then $f(n) = \frac{f(n)}{g(n)}\cdot g(n) \leq C' \cdot g(n)$, since $C' \geq \frac{f(n)}{g(n)}$.

Therefore, you have what you want: there exists a constant $C'>0$ such that $f(n) \leq C'\cdot g(n)$ for all $n\geq 1$.

Remark: we used the fact that $g$ is positive ($g(n) > 0$ for all $n$) to avoid division by $0$ when we define $C'$.