0

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$

amWhy
  • 209,954
KIMKES1232
  • 425
  • 3
  • 9
  • I forgot the O , thanks – KIMKES1232 May 13 '20 at 11:48
  • So what is your definition of $f(n)=O(g(n))$? – Martin R May 13 '20 at 11:49
  • 1
    tf(n)=O(g(n)) (big O notation) if exists a constant c>0 ; and a $n_1\in Naturals$ so that for $n>n_1$ f(n)<=c∗g(n) – KIMKES1232 May 13 '20 at 11:53
  • so your definition is that $f \in \mathcal O(g)$ iff $\exists c \in \mathbb R, N \in \mathbb N$ such that $f(n) \le cg(n)$ for all $n > N$. Now, the definition in your post clearly implies this. To show the converse, choose a $c$ that works for all $n > N$, and think of how you can choose a bigger constant $c'$ such that $f(n) \le c' g(n)$ is guaranteed for all $1 \le n \le N$ – Brevan Ellefsen May 13 '20 at 12:03

2 Answers2

1

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

Clement C.
  • 67,323
0

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

zkutch
  • 13,410
  • "Positive" means you can't have $g(n)=0$. – Clement C. May 31 '20 at 23:50
  • @Clement C. Firstly: it depends on source used. Look, please, at https://en.wikipedia.org/wiki/Sign_(mathematics) and find "Terminology for signs" and there "strictly positive" vs "positive". Different sources may use different terminology. Second: of course, for $f>0$ functions my example not work. – zkutch Jun 01 '20 at 00:03
  • I am French, where "positif" means $\geq 0$. I am aware of the differences between languages. All I'm saying is that the standard meaning of "positive" in English, in a mathematical context, is $>0$. The same way that "greater" means $>$, not $\geq$. – Clement C. Jun 01 '20 at 00:20
  • Same is for "greater" vs "strict greater", again is possible to look at https://en.wikipedia.org/wiki/Strict . I did not see standards in this case - some authors use one definition, others another. It's, of course, not very convenient. – zkutch Jun 01 '20 at 00:36
  • https://math.stackexchange.com/questions/18464/is-positive-the-same-as-non-negative, https://en.wikipedia.org/wiki/Positive_real_numbers, etc. Anyways. – Clement C. Jun 01 '20 at 01:29
  • Anyways it doesn't create "standard". I more value mathematical results, even little: I add some generalization to $f>0$ case. More nice is to make next step, no? – zkutch Jun 01 '20 at 05:49
  • Let us continue this discussion in chat. – zkutch Jun 01 '20 at 18:26