2
$\begingroup$

TRUE or FALSE:

For two positive functions $f(n)$ and $g(n)$, $f(n)$ has to be either $O(g(n))$ or $\Omega(g(n))$ or both.

I feel like using $\sin$/$\cos$ for $f$ and $g$ would be a way of showing this is false, but I don't understand how to go about proving it.

  • 0
    $sin$ and $cos$ are NOT posetive functions2012-09-27

1 Answers 1

2

Let $f(n)=n$ when $n$ is odd, and $n^2$ when $n$ is even.

Let $g(n)=n^2$ when $n$ is odd, and $n$ when $n$ is even.

The proof that this is a counterexample should not be hard. To begin, note that $f(n)$ cannot be $O(g(n))$, since for any constant $K$ there are arbitrarily large $n$ such that $f(n)\gt Kn$, namely any even $n$ larger than $K$. I will leave the other part to you. The argument is similar.

  • 0
    I dont really understand your definitions of f and g. how is n=n when n is odd and n^2 when n is even? (and vice versa for g)2012-09-27
  • 0
    It is $f(n)=n$ if $n$ is odd, and $n^2$ if even. So $f(1)=1$, $f(2)=4$, $f(3)=3$, $f(4)=16$, $f(5)=5$, $f(6)=36$, and so on. If you prefer, we can use $n^2$ and $n^3$, or many related functions. The point is to make $f(n)$ alternately much bigger and much smaller than $g(n)$.2012-09-27
  • 0
    ok cool, i see how it works for a certain case. You did the big o contradiction above, is big omega the opposite?2012-09-27
  • 0
    Yes, big omega goes bad at the odds. Quite symmetric!2012-09-27
  • 0
    couldn't you just pick a K that makes the inequalities true?2012-09-27
  • 0
    There is no $K$ that will work for all even $n$, or even for all big enough even $n$(for the $O$ part) since if $n$ is big, $\frac{n^2}{n}$ is bigger than $K$. Similar for the $\Omega$, except we are working on the odds.2012-09-27
  • 0
    does n have to be larger than k? is that part of the proof?2012-09-27
  • 0
    Yes, that is part of the formal proof. You want to show that **given** $K$, there is no $N$ such that if $n \gt N$, then $f(n)\lt Kg(n)$.2012-09-27
  • 0
    For the Ω side, we have to show f(n)> kn. So this is for the odds. how do prove the complete opposite as before?2012-09-27
  • 0
    It really is **exactly** the same, except that you consider odd $n$.2012-09-27