80 views
Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set.
| 80 views

+1 vote

Let's assume $\space \exists \space f(n) \in o(g(n)) \space \cap \omega(g(n))$.

By definition of $f(n) = o(g(n))$, we have,

$f(n) < c \cdot g(n) \space \forall \space c \in R_{0}$

where $R_{0}$ is a set of positive real numbers.

Now, by definition of $f(n) = \omega(g(n))$, we have,

$f(n) > c \cdot g(n) \space \forall \space c \in R_{0}$

Combining above two inequalities,

$f(n) < c \cdot g(n) < f(n)$ which is a contradiction, since a value cannot be strictly greater and smaller than another value, at the same time.

Hence, the above inequality does not hold for all positive real values of constant $c$.

Hence, $o(g(n)) \space \cap \omega(g(n)) = \emptyset$.

Another way to prove by using the limits definitions

Let's assume $\space \exists \space f(n) \in o(g(n)) \space \cap \omega(g(n))$.

Which means, $f(n) \in o(g(n))$ and $f(n) \in \omega(g(n))$.

Now, according to definition of $f(n) \in o(g(n))$,

$\lim_{n \rightarrow \infty }{\frac{g(n)}{f(n)} } = \infty$

which means, $\lim_{n \rightarrow \infty }{\frac{1}{\frac{g(n)}{f(n)} } }= 0$

which means,  $\lim_{n \rightarrow \infty }{\frac{f(n)}{g(n)} }= 0$

Now, according to the definition of  $f(n) \in \omega(g(n))$,

$\lim_{n \rightarrow \infty }{\frac{f(n)}{g(n)} }= \infty$

Which is a contradiction since one definition says the limit evaluates to infinity, while other says it evaluates to zero.

Hence, no such function $f(n)$ exists.

Hence,  $o(g(n)) \space \cap \omega(g(n)) = \emptyset$.

by Active (2.2k points)
edited
0
constant 'c' can be different in both cases.. Right ?
0
Yes, but the inequality must hold for all values of c.
0

@toxicdesire here, $f(n) < c_{1}g(n) \;, \forall \; c_{1}\in \mathbb{R}$ and $f(n) > c_{2}g(n) \;, \forall \; c_{2}\in \mathbb{R}$

Now, $c_{2}g(n)<f(n) < c_{1}g(n)$ , $\forall \; c_{1},c_{2}\in \mathbb{R}$

Now, how to prove that no positive real  $c_1,c_2$ exist ?

+1

We don't need to prove that no positive real $c_{1}, c_{2}$ exist. Clearly, inequality holds if $c_{2} < c_{1}$ as in your case.

We have to prove that the inequality holds for all positive real $c_{1}, c_{2}$. Does it hold if $c_2 > c_{1}$ for the same $c_{1}, c_{2}$? It doesn't. Hence contradiction. Am I correct, and should I add this to the answer too? or it's okay if I don't?

+1
yes, correct. It will be good if you add it...

another way to prove it by using calculus :-

I Assume a function $f(n) \in o(g(n)) \cap \omega (g(n))$

It means $1)$ $f(n) \in o(g(n))$ and  $2)$ $f(n) \in \omega (g(n))$

According to defintion of $f(n) \in o(g(n)) ,$

$\lim_{n\rightarrow \infty }\frac{g(n)}{f(n)} = \infty$

and According to defintion of  $f(n) \in \omega (g(n)),$

$\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)} = \infty$

but $\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)}$ should approaches to zero. So, it means no $f(n)$ exist which satisfy both conditions $(1)$ and $(2)$ simultaneously. So, $f(n) \notin o(g(n)) \cap \omega (g(n))$
+1