If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$? Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$.

If the statement is true, then can anyone provide a counterexample for when any of the two conditions in bold are relaxed.

If the statement is false, can someone provide a counterexample to show why

I believe that the statement is true and my attempt at the proof is by assuming without loss of generality that $f\notin O(g)$

$f\notin O(g)\implies\neg(\exists N\in\mathbb{N}$ s.t $f(n)\leq Cg(n)$, for some $C&gt;0$ and $\forall n&gt;N)$

$\implies\forall N\in\mathbb{N}\space,\space f(n)&gt;Cg(n)$, for some $C&gt;0$ and $\forall n&gt;N$

Have I negated the expression correctly, because I can't see how I can get $g\in O(f)$ from this expression
If $f = O(g)$, then

$$\exists n_0. \exists c. \forall n. (n &gt; n_0 \rightarrow f(n) \le c g(n))$$

The negation of this statement is

$$\forall n_0. \forall c. \exists n. (n &gt; n_0 \land f(n) &gt; c g(n))$$

This doesn't match your negation, so I believe your proof is incorrect.

I actually think the statement you're trying to prove is false. Try constructing functions f and g so that f is double g for a while, then g overtakes f and is triple f for a while, the f overtakes g and is quadruple g for a while, etc. Could you show that neither function is O of the other?

Hope this helps!