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?

$\endgroup$
0

1 Answer 1

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

$\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$ 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 you have read our privacy policy.

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