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

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

• Use the fact that $\log a + \log b = \log (ab)$. – adrianN Oct 25 '17 at 12:04
$$\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).$$