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