This question already has an answer here:

I want to prove (or disprove) that

$$\sum_{i=1}^n\log_2 i = \Theta(n\log_2 n)\,,$$

but I totally get stuck with this example. May someone help me with that.


marked as duplicate by David Richerby, Evil, fade2black, Juho, Rick Decker Nov 9 '17 at 2:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Use the fact that $\log a + \log b = \log (ab)$. $\endgroup$ – adrianN Oct 25 '17 at 12:04
  • $\begingroup$ You can use LaTeX directly here (just put in dollars as you usually would), so I replaced your image with text. $\endgroup$ – David Richerby Oct 25 '17 at 12:57


$$\frac{1}{4}n\log_2n < \frac{1}{2}n(\log_2n-1) = \sum_{i=\frac{n}{2}}^{n}\log_2\frac{n}{2}<\sum_{i=1}^{n} \log_2i < \sum_{i=1}^{n} \log_2 n = n \log_2 n\,.$$


The LHS is $\log(n!)$, which is known, by Stirling's formula, to be asymptotic to $$\frac12\log(2\pi n)+n(\log(n) - 1).$$

You can conclude.


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