# What is the big O for $n^{\log n} + n!$?

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

• Sorry the question should be What is the big O for n^log(n) + n!? – gauchopig Oct 16 '20 at 16:30
• By intuition, one has n in the exponent, and one has log n. Most definitely not the same. – gnasher729 Oct 16 '20 at 17:25
• 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. – gnasher729 Nov 15 '20 at 22:48

$$(\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}}$$.
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!)$$