2
$\begingroup$

My teacher claim these two are the same in a proof, but I'm not sure if this is correct. Could anyone shed me some lights?

$$\log_2((\lceil \log_2{n} \rceil)!) = \log_2(n) \cdot \log_2(\lceil \log_2(n) \rceil)$$

The original proof was $$O(\lceil \log_2(n) \rceil !) > O(n^k)$$ as $n \rightarrow \infty$

1 Answers 1

1

As a general rule, you have: $$ \log(n!) = \Theta(n \log n) $$ and the equality that you asked for is a special case of the above.

To prove this, you just need to prove the following bounds (for sufficiently large $n$, if needs be): $$ c_{\mathrm{low}} n \log n \leq \log(n!) \leq c_{\mathrm{up}} n \log n $$

For the lower bound, observe that:

$$ \log(n!) = \sum_{k=1}^n \log k \geq \sum_{k=n/2}^n \log k \geq \frac{n}{2} \log \frac{n}{2} = \frac{n}{2} \left( \log n - \log 2 \right) \simeq \frac{1}{2} n \log n$$ What we did was basically to choose the largest half of the elements and approximate them by their minimum.

Thus, you can take $c_{\mathrm{low}} \simeq \frac{1}{2}$ (a little less than $\frac{1}{2}$ to account for $\log 2$ that we lost, and that we cheated a assuming that $n$ is even).

For the upper bound, just notice that: $$ \log(n!) = \sum_{k=1}^n \log k \leq \sum_{k=1}^n \log n = n \log n$$ Thus, you can just take $c_{\mathrm{up}} = 1$ and you are done.

  • 0
    You might also want to take a look at the section of Wikipedia's article on *Factorial* entitled *Rate of growth and approximations for large n*. Link: http://en.wikipedia.org/wiki/Factorial2012-09-15
  • 0
    I wonder if you're solving the correct problem since the factorial part is for $\lceil \log_2(n) \rceil!$ but not $n!$.2012-09-15
  • 0
    I think I am. Take $N := \lceil \log_2(n) \rceil$. Then your question is about the approximation $\log (N!) \simeq N \log N$, which is what I was considering. Perhaps it was confusing of me to also use $n$, though ($n$ in my answer corresponds to $N$ in this comment).2012-09-15
  • 0
    Got it, sorry for the confusion. Thanks.2012-09-16
  • 0
    No problem; always pleased to be able to help ;)2012-09-16