An algorithmic and complexity analysis of interpolation search

DOI10.1007/BF00288534zbMath0405.68057MaRDI QIDQ1257344

Gaston H. Gonnet, Lawrence D. Rogers, J. Alan George

Publication date: 1980

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

Computational Complexity; Analysis of Algorithms; File; Interpolation Search Algorithm; Ordered Tables; Vector Search

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P05: Data structures

68P20: Information storage and retrieval of data

68R99: Discrete mathematics in relation to computer science

68W99: Algorithms in computer science

Related Items

Fast search algorithms for look‐up tables, Two-way chaining for non-uniform distributions, New trie data structures which support very fast search operations, Interpolation-binary search, Jump interpolation search trees and symmetric binary numbers, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Simulating interpolation search, Batched interpolation searching on databases, Parallel processing can be harmful: The unusual behavior of interpolation search, Log-logarithmic worst-case range queries are possible in space theta(N), Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The interpolation-sequential search algorithm
• Understanding the complexity of interpolation search
• Notes on the derivation of asymptotic expressions from summations
• Interpolation search—a log log N search