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
    No problem; always pleased to be able to help ;)2012-09-16