2
$\begingroup$

What is the time complexity of

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

and how do you calculate it?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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