I have been using the big O notation for some time now and know that, for example, $(e^x)^2 \in o(e^{x^2})$. In general, if $f$ grows faster than $g$, then $f(g(x))$ grows faster than $g(f(x))$. Does this hold in general? If so, how can I prove this? I was not able to find such proof anywhere. If not, does something similar hold, which would imply examples such as the one mentioned?

The version with "$f(g(x))$ grows strictly faster than $g(f(x))$" clearly does not hold (as correctly pointed out by Brian). Does the non-strict version hold?


It definitely does not hold in general. Let $f(x)=x^2$ and $g(x)=x$; then


so $g(x)\in o(f(x))$, but $g\circ f=f\circ g$.

Taking $f(x)=1$ and $g(x)=\frac1x$ yields a similar example.

  • 2
    $\begingroup$ +1 Thanks prof. Brian! I dont understand why this answer got two downvotes. This answer perfectly answers OPs question. In a sense, it is vandalism to downvote an answer of this quality. $\endgroup$
    – James
    Apr 10 '20 at 22:18
  • 1
    $\begingroup$ @James: You’re welcome! $\endgroup$ Apr 10 '20 at 22:20
  • $\begingroup$ @James, it does not. Namely, the part "If not, does something similar hold...", which I assume does, as I have written in the edit. While I am grateful for this answer, it does not resolve the original question and only answers the not-so-interesting part while keeping the main thing unanswered. $\endgroup$ Apr 11 '20 at 16:31
  • 1
    $\begingroup$ @user2316602: Agreed. It is, however, a correct answer to part of your question, and I have to admit that I, like James, find the downvotes a bit odd. (The other part really does seem quite non-trivial, though this is hardly my field.) $\endgroup$ Apr 11 '20 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.