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.

I do not know much about O notation so could you please help me, I have to prove or disprove the following statment:

$\forall f,g: \mathbb{N} \rightarrow \mathbb{R}_{\geq 0} \text{ }f=O(g) \text{ or } f=\Omega(g)$

Can I disprove this statement with $f = \sin(x) + 1 $ and $ g = \cos(x) + 1$?

Thanks in advance! Cheers

share|improve this question
    
Are you taking $R_+$ to mean the positive reals or the nonnegative reals? –  only Oct 13 '12 at 21:32
    
Yes, this is essential, it is about nonnegative reals. Already edited –  haemhweg Oct 13 '12 at 21:34
add comment

1 Answer

up vote 3 down vote accepted

Your proposed example will do the job in a fairly straightforward way if you measure angles in degrees.

If you are working in radians, which is the usual convention in mathematics unless one says otherwise, it can be done. But we need to find out quite a lot about how sine and cosine behave at the integers. Not easy! Replacing the $n$ in $\sin n$ and $\cos n$ by $\frac{\pi n}{2}$ will work.

There are simpler examples that disprove the assertion. We can let $f(n)=0$ when $n$ is even, $f(n)=1$ when $n$ is odd, and let $g(n)=1-f(n)$.

Or for an example that is slightly more realistic in a computing context, let $f(n)=n$ when $n$ is even, $f(n)=n^2$ when $n$ is odd, and let $g(n)=n^2$ when $n$ is even, $g(n)=n$ when $n$ is odd.

share|improve this answer
    
Thank you! Actually I needed a periodic function in integers with the same period and your mentioned functions demonstrate falsity of statement way better. –  haemhweg Oct 13 '12 at 21:51
add comment

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.