# Code Run Time Proof

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.

-
$sin$ and $cos$ are NOT posetive functions – Belgi Sep 27 '12 at 0:37

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.

-
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 1: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 1: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 2:20
Yes, big omega goes bad at the odds. Quite symmetric! – André Nicolas Sep 27 '12 at 2:23
couldn't you just pick a K that makes the inequalities true? – John Sep 27 '12 at 2:29