Big O and Omega Properties

Question

I am trying to think of a case where this is not true:

$f(n) = O(g(n))$ and $f(n) \neq \Omega(g(n))$, does $f(n) = o(g(n))$?

I suspect that it has to do with the varying $c$ and $n_{0}$ constants but am not completely sure.

Thanks!

Answer 1

Consider $f(n) = n+(-1)^nn$ and $g(n) = n$.

Answer 2

You can read the relations this way.

• $f \in O(g)$ means that $f$ eventually stays below some multiple of $g$.
• $f \in \Omega(g)$ means that $f$ eventually stays above some multiple of $g$.
• $f \in o(g)$ means that $f$ eventually stays below any multiple of $g$.

So if $f\not\in \Omega(g)$, $f$ must dip below any particular multiple of $g$ infinitely often. But that doesn't mean it stays below that multiple. And knowing that $f\in O(g)$ doesn't help much; that just means $f$ doesn't dominate $g$. So a counterexample to your question, for instance, is obtained by taking $g(n)=1$ everywhere, $f(n)=1$ for even $n$, and $f(n)=1/n$ for odd $n$. Then $f$ is $O(g)$ (it's $\le g$), it's not $\Omega(g)$ (it dips below any constant infinitely often), and it's not $o(g)$ (it doesn't stay below $g/2$, say).