1
$\begingroup$

Using Stirling's approximation, we have $\log_{2} (n!) = n\log_{2} n - (log_{2} e)n + O(log_{2}n)$. Most lecture notes I have come across say that $ n\log_{2} n - (log_{2} e)n + O(log_{2}n) = \Omega (n\log_{2} n)$. Can someone give a rigorous proof of the last line using the basic definitions of big-O and big-Omega?

Thank you in advance.

P.S. There are similar posts on this and I know some other proofs of $\log (n!) = \Omega(n\log n)$ with or without using Stirling's approximation. I don't have any problem with $\log (n!) = \Omega(n\log n)$. It's just that I can't see why $ n\log_{2} n - (log_{2} e)n + O(log_{2}n) $ is $ \Omega (n\log_{2} n)$.

$\endgroup$
  • $\begingroup$ $n\lg n - O(n) + O(\lg n) = (n\lg n)(1-o(1))$, and $f(n)(1-o(1)) = \Omega(f(n))$ for well-behaved functions $f$. $\endgroup$ – András Salamon Feb 12 '17 at 12:00
0
$\begingroup$

A function $f(n)$ is said be $\Omega(g(n))$ if there exist $c,n_0\gt 0$ such that $f(n)\ge cg(n)\ge 0$ for all $n\ge n_0$.

A function $f(n)$ is said be $\mathcal O(g(n))$ if there exist $c,n_0\gt 0$ such that $0\le f(n)\le cg(n)$ for all $n\ge n_0$.

Here, $$\log_2(n!)=n\log_2 n-(\log_2 e)n+\mathcal O(\log_2 n)$$

Let $f(n)=\mathcal O(\log_2 n)$ such that $$\log_2(n!)=n\log_2 n-(\log_2 e)n+f(n)$$

By definition, $f(n)\ge 0$.

Thus, $$\begin{align}\log_2(n!)&\ge n\log_2 n-(\log_2 e)n\end{align}$$

We want to find some constants $c,n_0\gt0$ such that $$n\log_2n-(\log_2e)n\ge cn\log_2 n$$ for all $n\ge n_0$, that is, it must satisfy, $$(1-c)n\log_2n\ge (\log_2e)n$$ As $n\gt 0$, it must satisfy $$(1-c)\log_2n\ge (\log_2e)$$ Note that $$(1-c)\log_2n\ge(1-c)\log_2n_0$$ for all $n\ge n_0$. So, we need a positive $c$ and a $n_0$ to satisfy $$(1-c)\log_2n_0\ge (\log_2e)$$ This is easily possible, as the RHS is a constant and the LHS can be made large by choosing $n_0$ and $c$ appropriately. For instance, choosing $c=0.1$ and $n_0=4$ works.

Thus, by definition, $$\log(n!)=\Omega(n\log n)$$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Ah...that was simple!! I was making things complicated with hand-waving arguments...Thank you!! :) $\endgroup$ – user66261 Feb 12 '17 at 16:59
  • $\begingroup$ A small thing....$f(n)$ is general may not be positive, right? However, in this case, the $O(\log n)$ term is actually $1/2 \log (2 \pi n)$, so no probs. $\endgroup$ – user66261 Feb 12 '17 at 17:24
0
$\begingroup$

You really don't need Stirling's approximation.

Upper limit for log (n!): n! is the product of n numbers, all with a logarithm ≤ log n.

Lower limit for log (n!): n! is the product of n numbers, half of which are ≥ $n^{1/2}$ if n ≥ 4, which makes the logarithm ≥ log n / 2.

So for n ≥ 4, (n log n) / 4 ≤ log (n!) ≤ n log n.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I'll write $\log$ for $\log_2$, since that's the only kind of log we care about, here.

We have $\log n! = n\log n + c\log n + O(\log n)$, where $c=\log \mathrm{e}$ is positive. So, there's a constant $d$ such that, for all sufficiently large $n$, we have

$$n\log n + \log n - d\log n \leq \log n! \leq n\log n + c\log n + d\log n\,.$$

For all $n\geq c$, $0\leq c\log n\leq n\log n$. For all $n\geq 2d$, $\tfrac12n\log n\geq d\log n$. This gives $$n\log n + 0 - \tfrac12n\log n \leq \log n!\leq n\log n + n\log n + \tfrac12n\log n\,,$$ which is to say, $$\tfrac12n\log n \leq \log n!\leq \tfrac52n\log n\,,$$ and we're done.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice.....thank you....i think it will be $n\log n$ instead of zero in the penultimate line. :) $\endgroup$ – user66261 Feb 12 '17 at 17:34
  • $\begingroup$ @Qmulonimbus No, what I wrote is correct, but I did two steps at once. $n\log n + 0 - \tfrac12n\log n\leq n\log n + cn\log n - \tfrac12n\log n\leq \log n!$. $\endgroup$ – David Richerby Feb 12 '17 at 18:24

Your Answer

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