# Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$

My instructor assigned a problem that asks us to determine which asymptotic bounds apply to a certain $$f(n)$$ for a certain $$g(n)$$, in my case $$f(n) = \lg(n!)$$ and $$g(n) = \lg(n^n)$$. For clarity, the convention we use in our class is that $$\lg = \log_2$$, the "binary logarithm".

I know that by Stirling's approximation, $$\lg(n!)$$ grows in $$O(n\lg(n))$$, and evaluating the limit $$\lim_{n \to \infty} \frac{n\lg(n)}{n\lg(n)} = C$$, some constant > 0, and so $$\lg(n!)$$ is in $$\theta(\lg n^n)$$.

$$\theta$$ also means that my $$f(n)$$ is is in $$O(g(n))$$ and $$\Omega(g(n))$$, but this does not mean that my $$f(n)$$ is in $$o(g(n))$$ or $$\omega(g(n))$$.

For that, I believe I would need to evaluate $$\lim_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$$, but I am not certain.

What strategy would I use to show that $$f(n)$$ is in $$o(g(n))$$ or $$\omega(g(n))$$? Would I evaluate $$\lim_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$$?

• Have you tried evaluating $\lim_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$, using Stirling's formula? Please edit the question to show your result. – Apass.Jack Feb 24 at 18:48
• I think so, and was left with $\lim_{n \to \infty} \frac{n\lg(n)}{n\lg(n)}$, which is constant. This convinced me that $\lg(n!)$ is in $\theta(\lg(n^n))$. – Bryan Porter Feb 24 at 18:59

You seem tot be trying to prove something that is false. If $$f=O(g)$$ then $$\lim_{n\to\infty}g/f > 0$$ so $$f\neq \omega(g)$$. Similarly, if $$f=\Omega(g)$$ then $$f\neq o(g)$$.
Since you already have that $$\lg n! = \Theta(\ln n^n)$$, that gives you big-$$O$$ and big-$$\Omega$$, which preclude little-$$\omega$$ and little-$$o$$, respectively.
• Perhaps a better formulation of my question would be how I might find the tight asymptotic bound of the function $\lg(n!)$? I know that since $f(n)$ is in $\theta(g(n))$, $f(n)$ is in both $O(g(n))$ and $\Omega(g(n))$. I'm really asking how I can determine if $lg(n^n)$ is a tight asymptotic bound of not, or if my function being in $\theta$ makes that a silly question. – Bryan Porter Feb 24 at 19:03
• "Tight" usually means big-$\Theta$, since that excludes using $o$ or $\omega$ to squeeze another function between $\lg n^n$ and $\lg n!$. – David Richerby Feb 24 at 19:13
• Ach, of course! Given a result that concludes big-$\theta$, does that then preclude $o$ or $omega$? – Bryan Porter Feb 24 at 19:20
• Yes, because big-$\Theta$ implies big-$O$ and big-$\Omega$, which preclude little-$\omega$ and little-$o$, respectively. (Edited to add that to the answer: the fact that you didn't pick it up means that I was being too oblique!) – David Richerby Feb 24 at 19:21
Or you observe that $$n!$$ Is the product of $$n$$ numbers, and of these $$n/2$$ are at least $$\sqrt{n}$$, so $$\log n! \geq (n/2) \log(n) / 2 = (n \log n) / 4$$, which shows it is not $$o(n \log n)$$.