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.

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|improve this question
    
Related: math.stackexchange.com/questions/199344/… –  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
add comment

1 Answer 1

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