Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$

Problem Detail: 

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

Asked By : Jessie

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10548