On the Average Case Complexity of Parallel Sublist Selection
| Title | On the Average Case Complexity of Parallel Sublist Selection |
| Publication Type | Technical Report |
| Year of Publication | 1991 |
| Authors | Pucci, G., & Zimmermann W. |
| Other Numbers | 653 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-91-023.pdf |
| Bibliographic Notes | ICSI Technical Report TR-91-023 |
| Abbreviated Authors | G. Pucci and W. Zimmermann |
| ICSI Publication Type | Technical Report |