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
    It really is **exactly** the same, except that you consider odd $n$.2012-09-27