Hands-On GPU Programming with Python and CUDA

A work-efficient parallel prefix algorithm

Before we continue with our new algorithm, we'll look at the naive algorithm from two perspectives. In an ideal case, the computational time complexity is O(log n), but this is only when we have a sufficient number of processors for our data set; when the cardinality (number of elements) of our dataset, n, is much larger than the number of processors, we have that this becomes an O(n log n) time algorithm.

Let's define a new concept with relation to our binary operator —the work performed by a parallel algorithm here is the number of invocations of this operator across all threads for the duration ...