On parallel searching (Extended Abstract)
Marc Snir · 1982
We investigate the complexity of seaching by comparisons a table of n elements on a synchronous, shared memory parallel computer with p processors. We show that O(lgn) steps are required if concurrent access to the same memory cell is not allowed, whereas only O(lgn/lgp) steps are required if simultaneous reads are allowed. We next show that it is possible to search in O(lg(n)/p) steps if more general operations are used.