2

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.

Michael Albanese
  • 99,526
John
  • 23

1 Answers1

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.

André Nicolas
  • 507,029
  • 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) – John Sep 27 '12 at 01:46
  • 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)$. – André Nicolas Sep 27 '12 at 01:55
  • ok cool, i see how it works for a certain case. You did the big o contradiction above, is big omega the opposite? – John Sep 27 '12 at 02:20
  • Yes, big omega goes bad at the odds. Quite symmetric! – André Nicolas Sep 27 '12 at 02:23
  • couldn't you just pick a K that makes the inequalities true? – John Sep 27 '12 at 02:29
  • 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. – André Nicolas Sep 27 '12 at 02:35
  • does n have to be larger than k? is that part of the proof? – John Sep 27 '12 at 02:48
  • 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)$. – André Nicolas Sep 27 '12 at 02:51
  • For the Ω side, we have to show f(n)> kn. So this is for the odds. how do prove the complete opposite as before? – John Sep 27 '12 at 02:55
  • It really is exactly the same, except that you consider odd $n$. – André Nicolas Sep 27 '12 at 02:58