1
$\begingroup$

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$.

  • 0
    @frustratedguy What are you trying to say?2012-09-27

1 Answers 1

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.