If $f \in \mathcal{o}(g)$, does $f \circ g \in \mathcal{o}(g \circ f)$?

Question

It's a widely known fact that $\lambda n. \left\lfloor \lg n! \right\rfloor \in \mathcal{O}(\lambda n. \left\lfloor \lg n \right\rfloor!)$. Is it also true (I tried and haven't found a counterexample so far) for all functions $f$ and $g$ satisfying $f \in \mathcal{o}(g)$, not just $f(n) = \left\lfloor \lg n \right\rfloor$ and $g(n) = n!$? If so, does the result still hold with $\mathcal{o}$ replaced by $\mathcal{O}\setminus\Theta$? And under what condition can the conclusion be strengthened with $\mathcal{o}$ or $\mathcal{O}\setminus\Theta$ in place of $\mathcal{O}$?

Answer 1

There is no relation between $f \circ g$ and $g \circ f$ in general.

• If $f(n) = n^2$ and $g(n) = n^3$, then $f \circ g = g \circ f$
• If $f(n) = \log n$ and $g(n) = n^2$, then $f \circ g \in o(g \circ f)$.
• If $f(n) = \log n$ and $g(n) = \sqrt n$, then $f \circ g \in \omega(g \circ f)$.

Answer 2

No. Try $f(x)=\sqrt x$ and $g(x)=x^2$.