
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