Accession Number : ADA114611

Title :   Parallel Interpolation Search.

Descriptive Note : Technical rept.,

Corporate Author : HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s) : Reif,John H

PDF Url : ADA114611

Report Date : Mar 1982

Pagination or Media Count : 18

Abstract : This paper concerns the problem of searching, with p parallel processors, for a given key in a random ordered table of size n. We propose a parallel interpolation algorithm which we show has expected time cost or equal log(1 + log (n)/log(p) + 0(1) and we prove this algorithm has optimal expected time cost within a constant additive term. (Author)

Descriptors :   *Algorithms, *Interpolation, *Searching, *Processing equipment, Parallel orientation, Costs, Random access computer storage, Constants, Distribution, Computations, Inversion, Binomials, Functions

Subject Categories : Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE