PARALLEL INTERPOLATION SEARCH.
Several articles have noted the usefulness of a retrieval algorithm called sequential interpolation search, and A. C. Yao and F. F. Yao have proven a lower bound log log N-O(1) showing that this algorithm is actually optimal up to an additive constant on unindexed files of size N generated by the uniform probability distribution. We generalize the latter to show log log N-log log P-O(1) lower bounds the complexity of any retrieval algorithm with P parallel processors for searching an unindexed file of size N. This result is surprising because we also show how to obtain an upper bound that matches the lower bound up to an additive constant with a procedure that actually uses no parallel processing outside its last iteration. Our paper thus establishes the result that parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness. Our theorems assume the file is generated by the uniform probability distribution.
