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})$?
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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}}$.
$\begingroup$
$\endgroup$
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!)$
