# What is the Time complexity of $\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$

What is the time complexity of

$$\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$$

and how do you calculate it?

• Refer to this post for an in-depth accurate description of the general method for the algorithm analysis cs.stackexchange.com/a/23594/113759 – CATALUNA84 Feb 21 '20 at 14:24
• Your question is actually not about time complexity. – Yuval Filmus Feb 21 '20 at 16:03
• Are you just asking for the closed form of this function? – ryan Feb 21 '20 at 18:40

We can split the sum:

$$S \;=\; \sum_{i=1}^n \left(1 + \lfloor \log_2 i \rfloor\right) \;=\; \sum_{i=1}^{n/2} \left(1 + \lfloor \log_2 i \rfloor\right) + \sum_{i=n/2}^{n} \left(1 + \lfloor \log_2 i \rfloor\right)$$

Then as a lower bound it is allowed to drop the first sum and only look at the second sum. Furthermore, we are allowed to replace $$i$$ in the loop body with just $$n/2$$, as $$i \geq n/2$$ in the second sum.

$$S \;\geq\; \sum_{i=n/2}^{n} \left(1 + \lfloor \log_2 n/2 \rfloor\right) \;\geq\; (n/2)\cdot\lfloor \log_2 n/2 \rfloor$$

$$S \;\geq\; (n/2)\cdot(\log_2 n - \log_2 2 - 1) \;\geq\; \frac{1}{2}n\log_2 n - n$$

$$S \in \Omega(n \log n)$$

As an upper bound we can replace $$i$$ in every term by $$n$$ and similarly to above we get:

$$S \;\geq\; n(1 + \log_2 n)$$

$$S \in O(n \log n)$$

Therefore we can conclude that asymptotically $$S \in \Theta(n \log n)$$.