Proving $(f \circ g)(n) \in O( (g \circ f)(n) ) $ given $f$ and $g$ are increasing functions

Question

I look at this question and determine that, by intuitive, this results to proving

$f(n) \in O(f^{-1}(n))$ for $f$ and $f^{-1}$ being increasing functions since $(f \circ g)(n)$ is the inverse of $(g \circ f)(n) $

If they are both increasing functions, by properties of inverse functions, there must be an intersection point since $f^{-1}$ has inverse coordinates from $f$.

Thus, since there it is an intersection point for the two functions we can conclude that $f(n) \notin O(f^{-1}(n))$ and, hence, $(f \circ g)(n) \notin O( (g \circ f)(n) ) $ for $\forall n \in N.$

My concern: I have a feeling my proof is too simple. If I am missing something or forgot something please feel free to comment below.

Answer 1

All you need is one counter-example, which David C. Ullrich has provided in the comments. I'll "answer-ify" his comment. Let \begin{align*} f(n)&=2^n\\ g(n)&=2n. \end{align*} Then both functions are increasing. However, $(f\circ g)(n)=2^{2n}$ is not Big O of $(g\circ f)(n)=2\cdot 2^n,$ as the former increases much faster than the latter.