What is the time complexity of
$$\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$$
and how do you calculate it?
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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)$.
