Prove that \(o(g(n)) \cap \omega(g(n))\) is the empty set.
Using Classical Definitions
By definition, \(o(g(n))\) is the set of functions \(f(n)\) such that \(0 \le f(n) < c_1g(n)\) for any positive constant \(c_1 > 0\) and all \(n \ge n_0\).
And, \(\omega(g(n))\) is the set of functions \(f(n)\) such that \(0 \le c_2g(n) < f(n)\) for any positive constant \(c_2 > 0\) and all \(n \ge n_0\).
So, \(o(g(n)) \cap \omega(g(n))\) is the set of functions \(f(n)\) such that,
\[0 \le c_2g(n) < f(n) < c_1g(n)\]Now, the above inequality cannot be true asymptotically as \(n\) becomes very large, \(f(n)\) cannot be simultaneously greater than \(c_2g(n)\) and less than \(c_1g(n)\) for any constants \(c_1, c_2 > 0\)
Hence, no such \(f(n)\) exists, i.e. the intersection is indeed the empty set.
Using Limit Definitions
We can use the limit definitions of \(o(n)\) and \(\omega(n)\) to draw same conclusion.
\[o(g(n)) = \lim_{n \to \infty} \frac {f(n)} {g(n)} = 0\]and
\[\omega(g(n)) = \lim_{n \to \infty} \frac {f(n)} {g(n)} = \infty\]Both of these cannot hold true as \(n\) approaches \(\infty\).
Hence, no such \(f(n)\) exists, i.e. the intersection is indeed the empty set.