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.

$\endgroup$

3 Answers 3

7
$\begingroup$

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

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Can you please elaborate on the last paragraph? $\endgroup$
    – Raphael
    Feb 1, 2012 at 6:22
  • $\begingroup$ @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? $\endgroup$
    – Srivatsan
    Feb 1, 2012 at 6:36
  • $\begingroup$ 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). $\endgroup$
    – Raphael
    Feb 1, 2012 at 11:28
  • $\begingroup$ @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... $\endgroup$
    – Srivatsan
    Feb 1, 2012 at 12:18
  • $\begingroup$ @Raphael: I simplified my counterexample a lot. Hopefully the new answer is better and easier to follow. Thanks for your feedback. $\endgroup$
    – Srivatsan
    Feb 1, 2012 at 12:49
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Maybe the answer can be fixed, but as written, this is not a counterexample: $|g(n)| = n |\sin n| \leqslant n = O(f(n))$. $\endgroup$
    – Srivatsan
    Jan 31, 2012 at 20:21
  • 3
    $\begingroup$ @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... $\endgroup$
    – Did
    Jan 31, 2012 at 21:32
  • $\begingroup$ @DidierPiau, thanks, I fixed my answer. $\endgroup$
    – Saeed
    Feb 1, 2012 at 5:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .