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

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.

-
Every $f$ and $g$ such that $f(n)=g(n)$ for every $n$ fulfill the condition written in your post. – Did Nov 11 '11 at 18:36
I have tagged it as computer-science + asymptotics, based on the previous tag and the "computer-sciency" "definitions"... – Aryabhata Feb 9 '12 at 23:00

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.
Actually, there is a counterexample to this: if $g(n)=0$ for every $n$ large enough, then $g(n)=o(g(n))$ and $g(n)=\omega(g(n))$ hence $o(g)\cap\omega(g)$ is not empty. – Did Nov 11 '11 at 20:59
@Didier Piau: In the definition given above this is not true. Also most definitions of $o$ and $\omega$ satisfy $f \not\in o(f)$ (or $f \not\in \omega(f)$). – Alexander Thumm Nov 13 '11 at 17:47
If you refer to the fact that your definitions ill-advisedly use strict inequalities, I agree. But then some $f$ are not in $\omega(f)$ and some $\omega(g)$ are empty, which is strange, and which explains why everybody uses large inequalities. Then, as I wrote, $f\in\omega(f)$ for every $f$ and $f\in o(f)$ for some $f$ (these are not and should not be matters of convention, pace your comment). By the way, to write that most definitions of $\omega$ satisfy $f\notin\omega(f)$ for every $f$ is... well, somewhat creative. Any reference? – Did Nov 13 '11 at 18:03
@Didier: At least, you have to admit the question of $0 \in o(0)$ is very much an edge case. :p – Hurkyl Mar 11 '12 at 0:19