On from Page 1 of these lecture notes it is stated in the final paragraph of the section titled CREW Mergesort:

Each such step (in a sequence of $\Theta(\log_2\ n)$ steps) takes time $\Theta(\log_2\ s)$ with a sequence length of $s$. Summing these, we obtain an overall run time of $\Theta((\log_2\ n)^2)$ for $n$ processors, which is not quite (but almost!) cost-optimal.

Can anyone show explicitly how the sum mentioned is calculated and the squared log result arrived at?


You want to compute this sum: $$ \sum_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( \frac{n}{{2}^{i}}\right) $$

This can be easily rewritten to: $$ \sum_{i=1}^{\mathrm{log}\left( n\right) }\mathrm{log}\left( n\right) - \sum_{i=1}^{\mathrm{log}\left( n\right) }i $$

The first term is clearly $(\log(n))^2$. The second term is $(\log(n))^2/2+o((\log(n))^2)$. Summed, the result is $\Theta((\log(n))^2)$.

  • $\begingroup$ Hi, thanks for the answer, very useful so far. I don't follow how you expanded the second term in the rewritten summation, can you please show this as explicitly as possible? $\endgroup$ May 9 '12 at 14:44
  • $\begingroup$ That is just because he forgot a factor $\log(2)$. Then it is basic operations on the $\log$. $\endgroup$
    – Gopi
    May 9 '12 at 15:13
  • $\begingroup$ @PaulCaheny: Every logarithm in this post (as is usual in the field of computer science) is base 2. Then, $\log(n/2^i) = \log(n) - \log(2^i) = \log(n) - i$. $\endgroup$
    – jpalecek
    May 9 '12 at 15:38
  • $\begingroup$ @PaulCaheny: $\sum_{i=1}^{\mathrm{log}\left( n\right) }i$ is arithmetic series, and a well known result says that $\sum_{i=1}^{n }i = (n+1) \cdot n/2$. $\endgroup$
    – jpalecek
    May 9 '12 at 15:42
  • 2
    $\begingroup$ TCS Cheat Sheet, at your service. $\endgroup$
    – Raphael
    May 9 '12 at 15:59

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.