Cormen Edition 3 Exercise 3.1 Question 7 (Page No. 53)

Question

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

Answer 1

Proof by contradiction 

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

Comments

constant 'c' can be different in both cases.. Right ?

---

Yes, but the inequality must hold for all values of c.

---

@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 ?

---

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?

---

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

---

@ankitgupta.1729 edited and added your solution too.