The Gateway to Computer Science Excellence

+1 vote

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

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,601 answers

195,856 comments

102,232 users