Big Omg(f1) subs of Big Omg(f2) iff f1 element BigOmg(f2)

[zzmanzz]

Homework Statement

I usually struggle with proofs and would appreciate some help with the following problem:

Prove the following fact:

\Omega(f_1) \subseteq \Omega(f_2) iff f_1 \in \Omega(f_2)

Homework Equations

\Omega(f_1) is the set of functions g s.t.
g(n) \geq c f_1(n) where n_1 \geq n_o

The Attempt at a Solution

[/B]
1. \Omega(f_1) = g_1 (n_1) \geq c f_1(n_1)
\Omega(f_2) = g_2 (n_1) \geq c f_2(n_2)

2. f_1 \in \Omega(f_2) = f_2(n) \geq c f_1(n)

2. implies that
g_2(n) \geq f_2(n) \geq c f_1(n)

which shows that \Omega(f_1) \subseteq \Omega(f_2) from 1.

Is this on the right track? Thanks

 

[mfb]

$\Omega(f_1) = g_1 (n_1) \geq c f_1(n_1)$

You can't set a set of functions equal to a single function.

$g_2(n) \geq f_2(n) \geq c f_1(n)$

Where would the first inequality come from?

Also be careful that you don't reuse "c" for different things.

 

[zzmanzz]

You can't set a set of functions equal to a single function.
Where would the first inequality come from?

Also be careful that you don't reuse "c" for different things.

Thank you for the response. I think I may have made a mistake in the notation so I went back to the textbook to make sure that everything is accurate for this Big Omega which provides an asymptotic lower bound for functions.

1.

\Omega(f_1) = \{ g_1(n) :\exists c_1, \exists n_0 , c_1 > 0, s.t. 0 \leq c_1 f_1 (n_1) \leq g_1 (n_1) \quad n_1 \geq n_0 \} \Omega(f_2) = \{ g_2(n) :\exists c_2, \exists n_0 , c_2 > 0, s.t. 0 \leq c_2 f_2 (n_2) \leq g_2 (n_2) \quad n_2 \geq n_0 \}

2.

f_1 \in \Omega(f_2) = \quad \exists c_3, \exists n_0 , c_3 > 0 \quad f_2(n_3) \leq c_3 f_1(n_3) \quad n_3 \geq n_0

Maybe here I can use a proof by contradiction and state that :

f_1 \notin \Omega(f_2)

implies 3.

\quad \exists c_3, \exists n_0 , c_3 > 0 \quad f_2(n_3) \geq c_3 f_1(n_3) \quad n_3 \geq n_0

but in order to have:

\Omega(f_1) \subseteq \Omega(f_2)

3 can't be true because this fould imply that f_2 is not a lower bound on f_1

 

[mfb]

Maybe here I can use a proof by contradiction and state that :

f_1 \notin \Omega(f_2)

implies 3.

\quad \exists c_3, \exists n_0 , c_3 > 0 \quad f_2(n_3) \geq c_3 f_1(n_3) \quad n_3 \geq n_0

It doesn't imply that. As an example, $f_1(x)=x^2 |\sin(\pi x/2)| \notin \Omega(x)$ but there is no $c_3, n_0$ where $x \geq c_3 f_1(n_3) \quad \forall n_3 \geq n_0$.

$\notin$ needs a bit more thought what it means.

 

[zzmanzz]

Thanks for the example - very helpful.

I think that
f_1 \notin \Omega(f_2)

means that f1 is not in the set of functions asymptotically bounded below by f2and implies

\forall c_1 > 0 ,n_0, \exists n > n_0 \quad c_1 f_2(n) > f_1(n)In this adjustment of the formula, we say that some n exists where this is not true. I think earlier I made the mistake of giving an asymptotic upper bound definition for the contradiction.

For your example:

f_1(x)=x^2 |\sin(\pi x/2)| \notin \Omega(x)

we would have:

c_1 x > x^2 |\sin(\pi x/2)|

which is true whenever the sin part is negative.

However, I think that this contradiction still works for the proof because we just showed that

f_1 \notin \Omega(f_2)
\forall c_1 > 0 ,n_0, \exists n > n_0 \quad c_1 f_2(n) > f_1(n)
can't have
\Omega(f_1) \subseteq \Omega(f_2)
where
f_2(n) > f_1(n)

 

[mfb]

That is good.

which is true whenever the sin part is negative.

The sine part has to be zero (note the absolute value of it - I wanted to avoid negative numbers), but the key point here is the existence of some n where the right side is small.

You'll have to show $f_1 \in \Omega(f_1)$ to complete that direction.
If $f_1 \notin \Omega(f_2)$ and $f_1 \in \Omega(f_1)$ then $\Omega(f_1)$ cannot be a subset of $\Omega(f_2)$.