I'm doing an algorithm problem goes like this.
Construct two functions $f$, $g$ : $\mathbb{R}^+\rightarrow\mathbb{R}^+$ satisfying,
- $f$, $g$ are continuous;
- $f$, $g$ are monotonically increasing;
- $f\neq O(g)$ and $g\neq O(f)$.
Now I'm wondering how all of these 3 conditions hold here. Is it possible there are any $f$ and $g$ exist? Thank you!
Such pairs of functions do exist, but are a bit unusual. If $f\neq O(g)$ then for every $x$ and $C$ there's $y>x$ such that $f(y)> Cg(y)$. In other words $f>Cg$ on an unbounded set. On the other hand we have to have $g>Cf$ on an unbounded set. So $f$ and $g$ have to trade places infinitely often while still increasing, and each must even get an arbitrarily long lead on the other. I claim you can do this with $f$ and $g$ both piecewise linear, $f$ constant on intervals of the form $[2n,2n+1]$ and $g$ constant on the other intervals, i.e. of the form $[2n+1,2n+2]$. Just take the slope of each function on the intervals on which it changes increasing sufficiently fast (e.g. exponential.) I'll leave the details to you, but feel free to ask for more clarification.