Are there functions so that $f(n) \notin \mathcal{O}(g(n))$ and $g(n) \notin \mathcal{O}(f(n))$?

Question

Note that the functions should be $\mathbb{N}_0 \rightarrow \mathbb{N}_0$.

So I was thinking about something like
$$f(x) = 1 + \sin(\frac{\pi x}{2})$$ $$g(x) = 1 + \cos(\frac{\pi x}{2})$$ which would work I guess.

However, would it still be possible if both functions had to be monotonic increasing (not necessary strictly!)?

Answer 1

Yes. Inductively: $f(1) = g(1) = 1$ and \begin{align*} f(2 \, n) &= f(2 \, n - 1) \\ g(2 \, n) &= n \, f(2 \, n) \\ g(2 \, n+1) &= g(2 \, n) \\ f(2 \, n+1) &= n \, g(2 \, n + 1) \end{align*} for $n \ge 1$.