prove(disprove) asymptotic exact bound (theta)
Asymptotically,

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