Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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

Your Answer


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.