0
$\begingroup$

By intuition $n^{\log n}$ should be as the same as $n!$. By Stirling's approximation, $n!=n^ne^{-n}\sqrt{2\pi n}$, which makes me think both are also the same. So, is this $O(n!)$ or $O(n^{\log n})$?

$\endgroup$
3
  • $\begingroup$ Sorry the question should be What is the big O for n^log(n) + n!? $\endgroup$ – gauchopig Oct 16 '20 at 16:30
  • $\begingroup$ By intuition, one has n in the exponent, and one has log n. Most definitely not the same. $\endgroup$ – gnasher729 Oct 16 '20 at 17:25
  • 1
    $\begingroup$ I would always recommend taking a spreadsheet and listing the values for 0 ≤ n ≤ 100. It's not foolproof but will often show you that your intuition was wrong. Assuming the logarithm is base 2, 20! > 225^log 225, and 30! > 1331^log 1331. $\endgroup$ – gnasher729 Nov 15 '20 at 22:48
0
$\begingroup$

Look at this

$$(\frac{n}{e})^{\log{n}} = \frac{n^{\log{n}}}{n} = n^{{\log{n}}-1}$$

And compare it with $(\frac{n}{e})^n$ (as $e^{\log{n}} = n$, because of $\log$ function property). By multiplying $n$ to the above eqautation you will get $n^{\log{n}}$. Hence, just we need to compare $n$ and $(\frac{n}{e})^{n-\log{n}}$. So, definitely, we will find that the growth of $n!$ is much higher than $n^{\log{n}}$.

$\endgroup$
0
$\begingroup$

Knowing $$n^n \leqslant (n!)^2 \Leftrightarrow n^{\frac{n}{2}}\leqslant n!$$ we can write $$\frac{n^{\log n}}{n!}\leqslant \frac{n^{\log n}}{n^{\frac{n}{2}}} \to 0$$ and so $n^{\log n} + n! \in O(n!)$

$\endgroup$

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.