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

Question

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

Answer 1

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.

Answer 2

You can use Stirling’s formula.

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