How one can prove $o(g(n)) \cap \omega (g(n))$ is empty?

874 Views Asked by At

From definition of $o$ and $\omega$

one states that $0 < c_1\cdot g(n) < f(n)$ for $n > n_0$ and some $c_1$ and another states that $0 < f(n) < c_2\cdot g(n)$ for $n > n_1$ and some $c_2$

It seems like there is no such function that satisfies condition. But i can't show this rigorously.

1

There are 1 best solutions below

4
On

Note, that the definition of $\omega(g)$ says (assuming you refer to ordinary landau notation, in which case you did not look up the definitions correctly): For every $c_1>0$, there is a $n_1$, such that for all $n > n_1$ we have $0 < c_1|g(n)| < |f(n)|$. $o(g)$ is defined similar.

For $c_1 = 2$ and $c_2 = 1$ a function $f \in \omega(g) \cap o(g)$ must satisfy $2|g(n)| < |f(n)| < |g(n)|$ for all $n > n_0$ and some $n_0$, which is clearly impossible.