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.
