18
$\begingroup$

Construct two functions $ f,g: R^+ → R^+ $ satisfying:

  1. $f, g$ are continuous;
  2. $f, g$ are monotonically increasing;
  3. $f \ne O(g)$ and $g \ne O(f)$.
$\endgroup$
  • 2
    $\begingroup$ Have you considered the possibility that such functions might not exist? $\endgroup$ – jmite Mar 16 '13 at 7:45
  • $\begingroup$ If both $f,g$ are logarithmico-exponential, then either $f=O(g)$ or $g=O(f)$. Most functions encountered in practice are of this form. $\endgroup$ – Yuval Filmus Mar 16 '13 at 14:44
16
$\begingroup$

There are many examples for such functions. Perhaps the easiest way to understand how to get such an example, is by manually constructing it.

Let's start with function over the natural numbers, as they can be continuously completed to the reals.

A good way to ensure that $f\neq O(g)$ and $g\neq O(f)$ is to alternate between their orders of magnitude. For example, we could define

$f(n)=\begin{cases} n & n \text{ is odd}\\ n^2 & n \text{ is even}\\ \end{cases}$

Then, we could have $g$ behave the opposite on the odds and evens. However, this doesn't work for you, because these functions are not monotonically increasing.

However, the choice of $n,n^2$ was somewhat arbitrary, and we could simply increase the magnitudes so as to have monotonicity. This way, we may come up with:

$f(n)=\begin{cases} n^{2n} & n \text{ is odd}\\ n^{2n-1} & n \text{ is even}\\ \end{cases}$, and $g(n)=\begin{cases} n^{2n-1} & n \text{ is odd}\\ n^{2n} & n \text{ is even}\\ \end{cases}$

Clearly these are monotone functions. Also, $f(n)\neq O(g(n))$, since on the odd integers, $f$ behaves like $n^{2n}$ while $g$ behaves like $n^{2n-1}=n^{2n}/n=o(n^{2n})$, and vice-versa on the evens.

Now all you need is to complete them to the reals (e.g. by adding linear parts between the integers, but this is really beside the point).

Also, now that you have this idea, you could use the trigonometric functions in order to construct ``closed formulas'' for such functions, since $\sin$ and $\cos$ are oscillating, and peak on alternating points.

$\endgroup$
  • $\begingroup$ Can we say that $f(n) \in O(n^{2n})$ and $g(n) \in O(n^{2n})$? $f(n)$ and $g(n)$ are as defined in your answer. $\endgroup$ – mayank Mar 17 '13 at 16:47
  • $\begingroup$ Yes. We can even say that $f(n)\le n^{2n}$ (similarly for $g$), which is stronger than $O$. $\endgroup$ – Shaull Mar 17 '13 at 18:15
-3
$\begingroup$

Good illustration for me is: http://www.wolframalpha.com/input/?i=sin%28x%29%2B2x%2C+cos%28x%29%2B2x

$$ f(n) =2x+sin(x) $$ $$ g(n) =2x+cos(x) $$ $$ f\neq O(g) $$ $$ g\neq O(f) $$

$\endgroup$
  • 5
    $\begingroup$ Actually they are both $O$ of each other. $\endgroup$ – Karolis Juodelė Mar 5 '14 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.