# prove(disprove) asymptotic exact bound (theta) [duplicate]

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 DeckerNov 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.

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

## 2 Answers

Asymptotically,

$$\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.