Proving $g(n)$ is $O(f(n))$ with given inequalities

[mathmari]

Hey!

I am asked to prove that $g(n)$ is $O(f(n))$ if $f(n)\geq \epsilon$ , for some $\epsilon>0$ and for all but some finite set of $n$ and there exist constants $c_1>0$ and $c_2>0$ such that $g(n)\leq c_1 f(n)+c_2$ for almost all $n\geq 0$.

$g(n)$ is $O(f(n))$ means that $\exists c>0, n_0\in \mathbb{N}$ such that $\forall n\geq n_0: g(n) \leq c f(n)$.

How could I prove that $g(n)$ is $O(f(n))$ if $f$ and $g$ satisfy the above inequalities?? (Wondering)

 

[I like Serena]

Hey!

I am asked to prove that $g(n)$ is $O(f(n))$ if $f(n)\geq \epsilon$ , for some $\epsilon>0$ and for all but some finite set of $n$ and there exist constants $c_1>0$ and $c_2>0$ such that $g(n)\leq c_1 f(n)+c_2$ for almost all $n\geq 0$.

$g(n)$ is $O(f(n))$ means that $\exists c>0, n_0\in \mathbb{N}$ such that $\forall n\geq n_0: g(n) \leq c f(n)$.

How could I prove that $g(n)$ is $O(f(n))$ if $f$ and $g$ satisfy the above inequalities?? (Wondering)

Hi! (Smile)So we are given that $g(n)\leq c_1 f(n)+c_2$.
And we need to find a $c$ such that we can ensure that $g(n) \leq c f(n)$.
Yes?Suppose we can find a $c$ such that $g(n)\leq c_1 f(n)+c_2 \leq c f(n)$.
Which condition would that impose on $c$? (Wondering)

 

[magneto1]

Let $M$ be the finite set where there are no constants $c_1, c_2$ where $g(n) \leq c_1f(n) + c_2$. To show $g \in O(f)$ by definition of $O()$, choose $c = c_1 + \frac{c_2}{\varepsilon}$, and let $n_0 = \max{M} + 1$.

 

[mathmari]

Suppose we can find a $c$ such that $g(n)\leq c_1 f(n)+c_2 \leq c f(n)$.
Which condition would that impose on $c$? (Wondering)

$c_1 f(n)+c_2 \leq c f(n) \Rightarrow (c-c_1)f(n) \geq c_2\Rightarrow f(n)\geq \frac{c_2}{c-c_1}$

We know that $f(n)\geq \epsilon$, for some $\epsilon >0$

From these two relations we can chose $$\frac{c_2}{c-c_1}=\epsilon\Rightarrow c=\frac{c_2+c_1\epsilon}{\epsilon}$$

Is this correct?? (Wondering)

 

[I like Serena]

$c_1 f(n)+c_2 \leq c f(n) \Rightarrow (c-c_1)f(n) \geq c_2\Rightarrow f(n)\geq \frac{c_2}{c-c_1}$

We know that $f(n)\geq \epsilon$, for some $\epsilon >0$

From these two relations we can chose $$\frac{c_2}{c-c_1}=\epsilon\Rightarrow c=\frac{c_2+c_1\epsilon}{\epsilon}$$

Is this correct?? (Wondering)

Yes. (Smile)

Slightly sharper:
$$c_1 f(n)+c_2 \leq c f(n) \quad\Rightarrow\quad c \ge c_1 + \frac{c_2}{f(n)} \ge c_1 + \frac{c_2}{\epsilon} $$
So the required relation is satisfied if we pick:
$$c \ge c_1 + \frac{c_2}{\epsilon} $$
(Nerd)

 

[mathmari]

Let $M$ be the finite set where there are no constants $c_1, c_2$ where $g(n) \leq c_1f(n) + c_2$. To show $g \in O(f)$ by definition of $O()$, choose $c = c_1 + \frac{c_2}{\varepsilon}$, and let $n_0 = \max{M} + 1$.

So is it as followed?? (Wondering)

We want to find $c>0$ and $n_0\geq 0$ such that $\forall n \geq n_0: g(n)\leq c f(n)$.

We know that there are constants $c_1>0$ and $c_2>0$ such that $g(n)\leq c_1 f(n)+c_2, \forall n \geq \max M +1$

$$\Rightarrow g(n)\leq \left ( c_1+\frac{c_2}{f(n)}\right ) f(n), \forall n\geq \max M +1$$

Let $N$ be the finite set where it does not stand that $f(n)\geq \epsilon$ for some $\epsilon>0.$
So, we have that $$g(n)\leq \left ( c_1+\frac{c_2}{\epsilon}\right ) f(n), \forall n\geq n_0$$
where $n_0=\max\{\max M+1, \max N+1\}$.

Choosing $c=c_1+\frac{c_2}{\epsilon}$ and $n_0=\max\{\max M+1, \max N+1\}$ we have that $g(n)\leq cf(n), \forall n\geq n_0$.

Is this correct?? (Wondering)

- - - Updated - - -

Yes. (Smile)

Slightly sharper:
$$c_1 f(n)+c_2 \leq c f(n) \quad\Rightarrow\quad c \ge c_1 + \frac{c_2}{f(n)} \ge c_1 + \frac{c_2}{\epsilon} $$
So the required relation is satisfied if we pick:
$$c \ge c_1 + \frac{c_2}{\epsilon} $$
(Nerd)

And do we find the $n_0$ as I wrote it above?? (Wondering)

 

[mathmari]

Yes. (Smile)

Slightly sharper:
$$c_1 f(n)+c_2 \leq c f(n) \quad\Rightarrow\quad c \ge c_1 + \frac{c_2}{f(n)} \ge c_1 + \frac{c_2}{\epsilon} $$
So the required relation is satisfied if we pick:
$$c \ge c_1 + \frac{c_2}{\epsilon} $$
(Nerd)

We have that $f(n)\geq \epsilon$, so shouldn`t it be $\frac{1}{f(n)}\leq \frac{1}{\epsilon}$??

 

[I like Serena]

And do we find the $n_0$ as I wrote it above?? (Wondering)

We would use the $n_0$ that applies to $g(n)≤c1f(n)+c2$. (Wasntme)

We have that $f(n)\geq \epsilon$, so shouldn`t it be $\frac{1}{f(n)}\leq \frac{1}{\epsilon}$??

You are right! (Blush)

We should pick $c$ such that:
$$c \ge c_1 + \frac{c_2}{\epsilon} \ge c_1 + \frac{c_2}{f(n)}$$

 

[magneto1]

Let $N$ be the finite set where it does not stand that $f(n)\geq \epsilon$ for some $\epsilon>0.$
So, we have that $$g(n)\leq \left ( c_1+\frac{c_2}{\epsilon}\right ) f(n), \forall n\geq n_0$$
where $n_0=\max\{\max M+1, \max N+1\}$.

There is no need to introduce $N$ in your proof, since $N$ is empty. You were given $f(n) \geq \varepsilon$ for all natural $n$. The reason why there is a $\max M + 1$ as I suggested is to find a $n_0$ where the bound will hold for $n > n_0$ (or sufficiently large $n$).

Note that the entire proof falls apart if there are infinitely many $n$ where you cannot find constants $c_1,c_2$ where $g \leq c_1 f + c_2$.

 

[mathmari]

We would use the $n_0$ that applies to $g(n)≤c1f(n)+c2$. (Wasntme)

Why do we not use also the $n_0$ that applies to $f(n)\geq \epsilon$ ?? (Wondering)

You are right! (Blush)

We should pick $c$ such that:
$$c \ge c_1 + \frac{c_2}{\epsilon} \ge c_1 + \frac{c_2}{f(n)}$$

I see! (Smile)

- - - Updated - - -

There is no need to introduce $N$ in your proof, since $N$ is empty. You were given $f(n) \geq \varepsilon$ for all natural $n$.

We are given that $f(n)\geq \epsilon $ for some $\epsilon>0$ and for all but some finite set of $n$.

Why is $N$ empty?? (Wondering)

 

[I like Serena]

Why do we not use also the $n_0$ that applies to $f(n)\geq \epsilon$ ?? (Wondering)

Because I was reading:

We are given that $f(n)\geq \epsilon $ for some $\epsilon>0$ .

It seemed to me that what came after belonged to the second condition, but perhaps it doesn't. (Doh)

 

[mathmari]

Because I was reading:

We are given that $f(n)\geq \epsilon $ for some $\epsilon>0$ .

It seemed to me that what came after belonged to the second condition, but perhaps it doesn't. (Doh)

It belongs to the first condition... (Blush)

So,do we have to take into consideration the set of $n$ for which it stands that $f(n)\geq \epsilon$?? (Wondering)

 

[I like Serena]

It belongs to the first condition... (Blush)

So,do we have to take into consideration the set of $n$ for which it stands that $f(n)\geq \epsilon$?? (Wondering)

Yes.
We need an $n_0$ such that both conditions are satisfied. (Sweating)

Pick the largest $n$ for which either of the conditions is not satisfied.
That should exist.
Then add $1$ and pick that as $n_0$. (Whew)

 

[mathmari]

Yes.
We need an $n_0$ such that both conditions are satisfied. (Sweating)

Pick the largest $n$ for which either of the conditions is not satisfied.
That should exist.
Then add $1$ and pick that as $n_0$. (Whew)

Ok! (Smile) Can we formulate it as I did in post #6?? (Wondering)

 

[I like Serena]

Ok! (Smile) Can we formulate it as I did in post #6?? (Wondering)

Sure. (Smile)

 

[mathmari]

Great! Thank you very much! (Bow)