If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?
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!