On the Average Case Complexity of Parallel Sublist Selection

TitleOn the Average Case Complexity of Parallel Sublist Selection
Publication TypeTechnical Report
Year of Publication1991
AuthorsPucci, G., & Zimmermann W.
Other Numbers653

The "Sublist Selection Problem" (SSP) is the following: Given an input list of nodes labeled True or False, extract the sublist of nodes labeled True. This paper analyzes the average case complexity of a parallel algorithm that solves SSP on the PRAM model of computation. The algorithm is based on the well-known "recursive doubling" technique. Doubly logarithmic upper and lower bounds are derived for the average number of iterations needed to produce the output list, under the assumption that all the nodes of the input list are marked False with prabability p, independently of the other nodes. Finally, the exact number of iterations (up to lower order terms) is established in the case that the input list is drawn from the uniform distribution over all possible labellings.

Bibliographic Notes

ICSI Technical Report TR-91-023

Abbreviated Authors

G. Pucci and W. Zimmermann

ICSI Publication Type

Technical Report