Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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: en.wikipedia.org/wiki/Factorial –  Feanor 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). –  Feanor 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 ;) –  Feanor Sep 16 '12 at 7:25

Your Answer

 
discard

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.