# Definition of PrefixSum function

I came across this paper and attempting to go through the implementation of randomized selection algorithm on page 8.

Step 1 of the algorithm suggest to compute $$s = PrefixSum(n_i, p)$$. Where $$p$$ is the number of processes and $$n_i$$ starts simply as a number of elements in each process. Page 4 has a definition of parallel prefix, but I do not understand how to apply it in the algorithm.

Example, let $$n_1 = 5, p = 2$$, what is $$PrefixSum(5,2)$$?

Thank you.

• Prefix sum is a very common operation in parallel algorithms, so there are many sources covering it. Did you check out any others, like Wikipedia? – Juho Oct 13 '18 at 22:03
• @Juho The only reasonable idea I came up with is similar to Wikipedia, i.e For process $P_2$, $PrefixSum(n_2, p) = n_1 + n_2$, but I am not sure whether that's correct, since this calculation is not a function of p, as in $PrefixSum(n_i, p) = n_1 + ... + n_i = f(i)$ – Paul Oct 13 '18 at 22:27