0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Feb 24 at 18:48
  • $\begingroup$ 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))$. $\endgroup$ – Bryan Porter Feb 24 at 18:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bryan Porter Feb 24 at 19:03
  • 1
    $\begingroup$ "Tight" usually means big-$\Theta$, since that excludes using $o$ or $\omega$ to squeeze another function between $\lg n^n$ and $\lg n!$. $\endgroup$ – David Richerby Feb 24 at 19:13
  • $\begingroup$ Ach, of course! Given a result that concludes big-$\theta$, does that then preclude $o$ or $omega$? $\endgroup$ – Bryan Porter Feb 24 at 19:20
  • 1
    $\begingroup$ 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!) $\endgroup$ – David Richerby Feb 24 at 19:21
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.