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
    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
    @DidierPiau, thanks, I fixed my answer.2012-02-01