4
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\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$
    – Paul Caheny
    May 9, 2012 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, 2012 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, 2012 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, 2012 at 15:42
  • 2
    $\begingroup$ TCS Cheat Sheet, at your service. $\endgroup$
    – Raphael ♦
    May 9, 2012 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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