[Solved]: Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort

Problem Detail: 

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?

Asked By : Paul Caheny

Answered By : jpalecek

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1754

3.2K people like this

 Download Related Notes/Documents