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

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
To prove that g(n) is O(f(n)), it is established that if f(n) is bounded below by a positive constant ε for all but a finite number of n, and there exist constants c1 and c2 such that g(n) ≤ c1 f(n) + c2 for almost all n, then g(n) can be shown to be O(f(n)). The proof involves selecting a constant c such that g(n) ≤ c f(n) for sufficiently large n. By manipulating the inequality g(n) ≤ c1 f(n) + c2, it is derived that c must satisfy c ≥ c1 + c2/ε. The choice of n0 is crucial and should be the maximum of the indices where the inequalities do not hold, plus one. This ensures that both conditions are satisfied for all n ≥ n0. The discussion emphasizes the importance of ensuring that both conditions regarding f(n) and g(n) are accounted for in the selection of n0.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Technology news on Phys.org
mathmari said:
Hey! :o

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)
 
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$.
 
I like Serena said:
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)
 
mathmari said:
$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)
 
magneto said:
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 - - -

I like Serena said:
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)
 
I like Serena said:
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}$??
 
mathmari said:
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)
mathmari said:
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)}$$
 
mathmari said:
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$.
 
  • #10
I like Serena said:
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)
I like Serena said:
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 - - -

magneto said:
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)
 
  • #11
mathmari said:
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)
 
  • #12
I like Serena said:
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)
 
  • #13
mathmari said:
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)
 
  • #14
I like Serena said:
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)
 
  • #15
mathmari said:
Ok! (Smile) Can we formulate it as I did in post #6?? (Wondering)

Sure. (Smile)
 
  • #16
Great! Thank you very much! (Bow)
 

Similar threads

Replies
7
Views
2K
Replies
8
Views
2K
Replies
4
Views
2K
Replies
2
Views
2K
Replies
1
Views
2K
Replies
3
Views
2K
Back
Top