Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort 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)$.