ON PARALLEL SEARCHING.

The author investigated the complexity of searching a sorted table of n elements on a synchronous, shared memory parallel computer with p processors. He showed 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 ( ROOT 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.