# Using limits to determine asymptotic bound

By using limits, show that log n! ∈ Θ(n logn).

Using Stirling's approximation for n! I get the limit: $$\lim_{n \to ∞} \frac{log({\sqrt{2πn}}*(\frac{n}{e})^n)}{nlogn} = constant > 0$$

When I break this down separately: $$\lim_{n \to ∞} \frac{\sqrt{2πn}}{n^n} * \lim_{n \to ∞} (\frac{n}{e})^n = constant > 0$$

To me, the left limit approaches 0 and the right limit approaches infinity. Can I not rewrite the limit like this? Or do I need to use L'Hopistal's rule? Because I don't understand how I would do that here.

• You dropped the logarithms and created an undefined limit. This leads you nowhere.
– user16034
Commented Oct 28, 2022 at 15:18
• @YvesDaoust O.o I was too quick and reading the question and I didn't realize that. In addition to your observation, the denominator of the first limit in the product is weird. Commented Oct 28, 2022 at 15:25

You have some algebra mistake but, in general, you are right that you cannot always rewrite a limit of products as the products of limits. Let $$f(n)$$ and $$g(n)$$ be two functions. Then $$\lim_{n \to \infty} f(n)g(n) = \lim_{n \to \infty} f(n) \cdot \lim_{n \to \infty} f(n)$$ only holds if $$\lim_{n \to \infty} f(n)$$ and $$\lim_{n \to \infty} f(n)$$ exist and are either both finite, or one is infinite and the other is not $$0$$.

To handle the original limit without using L'Hôpital's rule: \begin{align*} \lim_{n \to \infty} \frac{\log n!}{n \log n} &= \lim_{n \to \infty} \frac{\log (\sqrt{2\pi n} \cdot (n/e)^n )}{n \log n}\\ & =\lim_{n \to \infty} \frac{\log \sqrt{2\pi n}}{n \log n} + \lim_{n \to \infty} \frac{\log (n/e)^n }{n \log n} \\ &=0 + \lim_{n \to \infty} \frac{n \log n }{n \log n} - \lim_{n \to \infty} \frac{n \log e}{n \log n} =1 - 0 = 1. \end{align*}

Therefore $$\log n! \sim n \log n$$.

$$\log\left(\sqrt{2\pi n}\left(\dfrac ne\right)^n\right)=\log\sqrt{2\pi}+\frac12\log n +n\log n-n.$$

Clearly, this expression is dominated by the term $$n\log n$$ and your limit is $$1$$.

• This is a bit nitpicky, but since we don't know the base of the $\log$ you could replace the last term with $-n \log e$ to cover all bases (pun intended). Commented Oct 28, 2022 at 15:29
• @Steven: in calculus, $\log$ is usually natural.
– user16034
Commented Oct 28, 2022 at 15:45
• Everywhere, ln is always the natural logarithm. Should be used unless it doesn't matter. Commented Oct 28, 2022 at 16:51
• @gnasher729: for some reason, on Mathematics 99% of the posts use $\log$.
– user16034
Commented Oct 28, 2022 at 16:59
• Well, this is computer science, not mathematics. Commented Oct 29, 2022 at 22:09

You broke this down, but in a very unpractical way.

$$\log {(n/e)^n} = n \log (n /e) = n (\log n - 1)$$ is much more helpful.