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

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.

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}$$

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.

• Can you please elaborate on the last paragraph? Feb 1, 2012 at 6:22
• @Raphael: My notation is admittedly a little poor. Do you want a better explanation for the functions? Or do you want a proof that the pair of functions provides a counterexample? Feb 1, 2012 at 6:36
• The latter, if you'd be so kind. It is probably not hard, but not immediate (at least not to me). I have no problems with your notation (although the use of flooring brackets is arguably a bad idea). Feb 1, 2012 at 11:28
• @Raphael If $f(n)$ and $g(n)$ are the two functions. Evaluate $f(n) / g(n)$ at $n = (2k)!$ and $n = (2k+1)!$. This will show that $f(n)/g(n)$ takes arbitrarily large and arbitrarily small positive values... Feb 1, 2012 at 12:18
• @Raphael: I simplified my counterexample a lot. Hopefully the new answer is better and easier to follow. Thanks for your feedback. Feb 1, 2012 at 12:49

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$.

• Maybe the answer can be fixed, but as written, this is not a counterexample: $|g(n)| = n |\sin n| \leqslant n = O(f(n))$. Jan 31, 2012 at 20:21
• @Srivatsan is right that this does not work, but the idea that $g(n)$ could be abnormally small from time to time is a good one. Consider for example $f(n)=n\cos(n)$ and $g(n)=n\sin(n)$, then $f\notin O(g)$ and $g\notin O(f)$. This kind of construction has a simplicity I personally like. So, Saeed, your idea was a good one, which only needed to be pushed a little further...
– Did
Jan 31, 2012 at 21:32
• @DidierPiau, thanks, I fixed my answer. Feb 1, 2012 at 5:52