1
$\begingroup$

Problem

I've got the following statement which I'm looking to prove:

$\log_2(n!) \in \mathcal{O}(n \cdot \log_3(n))$

The question is: how to do it?

Steps taken so far

My approach so far was to apply a few laws regarding the logarithms as follows:

$\Leftrightarrow \left(\log_2(n!)\right) \in \mathcal{O}\left(n \cdot \log_3(n)\right)$

$\Leftrightarrow \left(\log_2(n!)\right) \in \mathcal{O}\left(\log_3(n^n)\right)$

$\Leftrightarrow \left(\frac{\ln(n!)}{\ln(2)}\right) \in \mathcal{O}\left( \frac{\ln(n^n)}{\ln(3)}\right)$

$\Leftrightarrow \left(\frac{1}{\ln(2)} \cdot \ln(n!)\right) \in \mathcal{O}\left( \frac{1}{\ln(3)} \cdot \ln(n^n) \right)$

Which approximately boils down to..

$\underline{\Leftrightarrow \left(1.44 \cdot \ln(n!)\right) \in \mathcal{O}\left( 0.91 \cdot \ln(n^n) \right)}$

Unfortunately, that's still not particularly helpful. Of course, I realize that $n^n$ is going to grow much faster than $n!$. Still, the natural logarithms combined with the constants are making it hard for me to estimate which of the two terms might be the "smaller" one.

Therefore, I'd greatly appreciate your ideas. In case we can't find a fully formal proof, a more informal one would certainly be helpful nevertheless.

$\endgroup$
  • $\begingroup$ Isn't the functionality of $ln$ such that it tapers off for any outrageous values? $\endgroup$ – T.Woody Nov 17 '18 at 22:14
  • $\begingroup$ Sure, it starts growing slower and slower with growing $x$-values, just like any logarithm I suppose. Still, I don't see how that would be helpful to answer this question? $\endgroup$ – StckXchnge-nub12 Nov 17 '18 at 22:19
  • $\begingroup$ It would help out because we know that we visually can see this be the case as we take a Lim to inifinity. $\endgroup$ – T.Woody Nov 17 '18 at 22:20
  • 1
    $\begingroup$ Supposing you know $n!=O(n^n)$ (easy to prove) then $log(n!)=O(log(n^n))$. Note $log(n^n)=n*log(n)$ and of course you can take care of the different basis of the log... $\endgroup$ – Marco Bellocchi Nov 17 '18 at 22:26
  • $\begingroup$ @T.Woody I see limited use in this. Sure, the $\ln$ keeps growing slower, but still, $\lim_{x \rightarrow \infty} (\ln(x)) = \infty$. It's not like we had reason to assume $\ln$ as constant after passing a certain $x$-boundary. $\endgroup$ – StckXchnge-nub12 Nov 17 '18 at 22:29

Your Answer

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

Browse other questions tagged or ask your own question.