patternMinor
Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort
Viewed 0 times
naivecrewmergesortasymptotictimelog_2nestedsquaredforparallel
Problem
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?
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?
Solution
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)$.
$$
\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)$.
Context
StackExchange Computer Science Q#1754, answer score: 5
Revisions (0)
No revisions yet.