# 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)$.
• That is just because he forgot a factor $\log(2)$. Then it is basic operations on the $\log$. – Gopi May 9 '12 at 15:13
• @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$. – jpalecek May 9 '12 at 15:38
• @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$. – jpalecek May 9 '12 at 15:42