Parallel processing can be harmful: The unusual behavior of interpolation search

DOI10.1016/0890-5401(89)90038-2zbMath0684.68067OpenAlexW1964185018MaRDI QIDQ1825662

Dan E. Willard, John H. Reif

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90038-2

zbMATH Keywords

parallel algorithmsexpected case time analysisinterpolation sort

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time

Cites Work

• New trie data structures which support very fast search operations
• Understanding the complexity of interpolation search
• An algorithmic and complexity analysis of interpolation search
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Design and implementation of an efficient priority queue
• Interpolation search—a log log N search
• On the Number of Successes in Independent Trials
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parallel processing can be harmful: The unusual behavior of interpolation search