3
$\begingroup$

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.

3 Answers 3

7

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

3

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.

  • 0
    Can you please elaborate on the last paragraph?2012-02-01
  • 0
    @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?2012-02-01
  • 0
    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).2012-02-01
  • 0
    @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...2012-02-01
  • 0
    @Raphael: I simplified my counterexample a lot. Hopefully the new answer is better and easier to follow. Thanks for your feedback.2012-02-01
  • 0
    That's much better, thanks! =)2012-02-01
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$.

  • 0
    Maybe the answer can be fixed, but as written, this is not a counterexample: $|g(n)| = n |\sin n| \leqslant n = O(f(n))$.2012-01-31
  • 3
    @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...2012-01-31
  • 0
    @DidierPiau, thanks, I fixed my answer.2012-02-01