is there a pair of functions that meets the next requirement?

Question

How i can find a pair of functions that meets the next requirement $f,g: \mathbb{N} \rightarrow \mathbb{R^+_0}$ And that $f(n) \not \in O(g(n))$ and $g(n) \not \in O(f(n))$ also these functions must be increasing functions. My hunch is that there are no pair of functions that meets these requierment but i dont know how to prove it.

Answer 1

Divide $\mathbb{N}$ in intervals $$I_1,I_2,\cdots$$ In $I_1$: $$f(n)=n,\qquad g(n)=n^2,$$ In $I_2$: $$f(n)=n^3,\qquad g(n)=n^2,$$ In $I_3$: $$f(n)=n^3,\qquad g(n)=n^4,$$ In $I_4$: $$f(n)=n^5,\qquad g(n)=n^4,$$ $$\cdots$$

Answer 2

I think such functions can indeed be found. Consider the following example: Both $f$ and $g$ have two consecutive values that are constant. $f$ jumps at even numbers and $g$ at odd numbers. Now let's construct $f$ and $g$ in such a way that:

• For even $n$ we construct the functions such that $g(n)=n f(n)$
• For odd $n$ the functions should satisfy $f(n) = n g(n)$

Both functions are increasing but none of these functions is in the limiting class of the other. Would that do the trick?