0
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Is the swapped order of $f \circ g$ and $g \circ f$ in your title intentional? $\endgroup$
    – orlp
    Commented Jul 18, 2022 at 15:26
  • $\begingroup$ Definitely intentional! $\endgroup$
    – ByteEater
    Commented Jul 18, 2022 at 18:10
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jul 18, 2022 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – ByteEater
    Commented Jul 18, 2022 at 20:59
  • $\begingroup$ "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 ? $\endgroup$
    – user16034
    Commented Jul 20, 2022 at 6:55

2 Answers 2

3
$\begingroup$

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)$.
$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Then both of the compositions are the identity function. A function is $\mathcal O$ of itself. So not a counterexample. $\endgroup$
    – ByteEater
    Commented Jul 18, 2022 at 18:11
  • $\begingroup$ 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. $\endgroup$
    – ByteEater
    Commented Jul 18, 2022 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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