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.