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.

Report Date:

1982-03-01

Pagination or Media Count:

18.0

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 log1 log nlogp 01 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