Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$sin$ and $cos$ are NOT posetive functions –  Belgi Sep 27 '12 at 0:37

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.