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

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}$$?

• Is the swapped order of $f \circ g$ and $g \circ f$ in your title intentional?
– orlp
Jul 18, 2022 at 15:26
• Definitely intentional! Jul 18, 2022 at 18:10
• Please ask only one question per post. If you have multiple questions, you can post them separately. It's confusing that the title doesn't match the body.
– D.W.
Jul 18, 2022 at 19:06
• They're so much related that I thought it'd be fine. (The alternative is to have multiple almost identical questions.) But I'm clearly not as versed in this community ad you are, so I'll try to remember. Yes, as I wrote in the comment under the first answer, I made a mistake in one character in the title. At SO they explained to me that edits shouldn't change what's asked, even to correct a glaring discrepancy, and even to say what was intended from the beginning. So I presume the same rule holds here. Jul 18, 2022 at 20:59
• "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!)$": widely ? Really ? And what is the connection to the question ? Jul 20, 2022 at 6:55

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)$$.
No. Try $$f(x)=\sqrt x$$ and $$g(x)=x^2$$.
• Then both of the compositions are the identity function. A function is $\mathcal O$ of itself. So not a counterexample. Jul 18, 2022 at 18:11
• Oh, I see I wrote o with the wrong capitalization in the title. Disregard it. (There's a rule that edits cannot change the essence, so it has to stay.) The body contains the actual problem I'm asking. Jul 18, 2022 at 18:14