# How are these two terms asymptotically equal?

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$

-

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.

-
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: en.wikipedia.org/wiki/Factorial – Jakub Konieczny Sep 15 '12 at 19:05
I wonder if you're solving the correct problem since the factorial part is for $\lceil \log_2(n) \rceil!$ but not $n!$. – IORI Sep 15 '12 at 19:35
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). – Jakub Konieczny Sep 15 '12 at 19:40
Got it, sorry for the confusion. Thanks. – IORI Sep 16 '12 at 6:33
No problem; always pleased to be able to help ;) – Jakub Konieczny Sep 16 '12 at 7:25