Using limits to determine asymptotic bound

Question

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.

Answer 1

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$.

Answer 2

$$\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$.

Answer 3

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.