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

Give examples of two continuous functions $f(n)$ and $g(n)$ of positive real inputs $n$, such that

  • $f(n)$ not equal to $O(g(n))$,
  • $g(n)$ not equal to $O(f(n))$,
  • $f(n)$ not equal to $Omega(g(n))$ and
  • $g(n)$ not equal $omega(f(n))$.

Hint: You can specify some of the values of $f(n)$ and/or $g(n)$ depending on some condition on $n$, such as when $n$ is even or odd, but make sure that your function is continuous and defined for all positive real $n$.

share|cite|improve this question
Related:… – Chris Eagle Sep 21 '12 at 16:18
Pythagoras it seems, paithyakara .... – user42831 Sep 27 '12 at 5:10
@frustratedguy What are you trying to say? – Willie Wong Sep 27 '12 at 10:53

In this context we usually want positive functions. It's natural to try a piecewise definition such as $f(n)=n$ when $n$ is odd and $f(n)=1$ when $n $ is even. You can then extend the definition to positive real by linear interpolation. An even quicker way is to employ the Pythagorean identity and let $f(n) = \sin^2 \pi n + n\cos^2 \pi n$. I'll leave it to you to check how this formula works and what $g$ should be.

By the way, the factor of $\pi$ is not really necessary for the function to have the desired properties, but it makes justification a lot easier.

share|cite|improve this answer

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.