Previous | Next --- Slide 19 of 49
Back to Lecture Thumbnails
Avesh

Assuming you have an infinite number of processors, to compute the scan of this array:

  1. Every processor in parallel adds two nodes. The first two elements are now complete.

  2. The first four elements are now complete.

  3. The first eight elements are now complete

etc.

If we have p processors instead of an infinite number, we divide the work w as:

$w / p$

$w = O(N \lg N)$

So we have each processor computing $(N/p) \lg N$