Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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: – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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