On parallel searching. (English) Zbl 0607.68047

Snir, Marc

SIAM J. Comput. 14, 688-708 (1985).

We investigate the complexity of searching a sorted table of n elements on a synchronous, shared memory parallel computer with p processors. We show that \(\Omega\) (lg n-lg p) steps are required if concurrent accesses to the same memory cell are not allowed, whereas O(lg n/lg p) steps are sufficient if simultaneous reads are allowed. The lower bound is valid even if only communication steps are counted, and the computational power of each processor is not restricted. In this model, \(\Theta\) (\(\sqrt{lg n})\) steps are required for searching when the number of processors is unbounded. If the amount of information that a memory cell may store is restricted, then the time complexity for searching with an unbounded number of processors is \(\Theta\) (lg n/lg lg n). If the amount of information a processor may hold is also restricted, then an \(\Omega\) (lg n) lower bound holds. These lower bounds are first proven for comparison- based algorithms; it is next shown that comparison-based algorithms are as powerful as more general ones in solving problems defined in terms of the relative order of the inputs.

MSC:

68P10	Searching and sorting
68Q25	Analysis of algorithms and problem complexity

Keywords:

parallel algorithms; parallel computations; complexity of searching a sorted table; comparison-based algorithms