How can I prove that $ f \notin \Omega (g) $ implies $ f \in \mathcal{O}(g) $?

Question

I'm asked to prove or disprove the following $$ f \notin \Omega (g) \Longrightarrow f \in \mathcal{O}(g). $$

I believe this is true since I thought a function would be either big-Oh of $g$ or big Omega of $g$, but I am having trouble proving it, as I cannot find a way of connecting the assumption with the conclusion.

Assumption: $ \forall c, n_0 \in \mathbb{R}^+, \exists n\in \mathbb{N}, n \geq n_0 \land f(n) < c\cdot g(n) $.

What we want to show: $ \exists c, n_0 \in \mathbb{R}^+, \forall n\in \mathbb{N}, n\geq n_0 \Longrightarrow f(n) \leq c\cdot g(n) $.

Thanks for you help.

Answer 1

You cannot conclude from $f\not\in\Omega(g)$ that $f\in\mathcal{O}(g)$.

To construct a counterexample, try picking some simple function $g$, choosing a function $f_1$ that grows much more slowly than $g$ and a function $f_2$ that grows much more quickly than $g$, and defining $f(2n+1)=f_1(2n+1)$, $f(2n)=f_2(2n)$.