If $g(n) \neq O(f(n))$, is $g(n) = \Omega(f(n))$?

Question

Given the positive functions $f(n), g(n)$, if $g(n)\neq O(f(n))$ then $g(n) = \Omega(f(n))$.

Is this correct?

I think not cause if $f$ does not set an upper limit to $g$ we can't be sure that the lower limit would be set by $f$. I mean that it can be lower than that.

Answer 1

You are correct: it’s not necessarily true. For an easy example take $$f(n)=\begin{cases} 2^n,&\text{if }n\text{ is odd}\\ 2^{-n}&\text{if }n\text{ is even} \end{cases}$$

and $$g(n)=\begin{cases} 2^n,&\text{if }n\text{ is even}\\ 2^{-n}&\text{if }n\text{ is odd}\;. \end{cases}$$

Answer 2

This is not true even with the additional restriction that $f$ and $g$ are monotone increasing. Take $f(n) = (\text{largest even number } \leq n)! $, and $g(n) = (\text{largest odd number } \leq n)!$. Then $$ \frac{f(n)}{g(n)} = \begin{cases} n, & \text{ if } n \text{ is even,} \\ \\ \frac{1}{n}, & \text{ otherwise,} \end{cases} $$ which takes arbitrarily large and arbitrarily small values. Thus $f$ and $g$ cannot be compared using the $O$ or $\Omega$ relations.

EDIT (Feb 1): Simplified the counterexample.

Answer 3

Simple example is $f(n) = n \cdot \cos(n), g(n) = n \cdot \sin(n)$, there is no $O, \theta, \Omega$ relation between $f$ and $g$.