Expected complexity of fast search with uniformly distributed data

DOI10.1016/0020-0190(81)90140-XzbMath0468.68061MaRDI QIDQ1156487

Gilbert N. Lewis, Nancy J. Boynton, F. Warren Burton

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

uniform distributionexpected valuebinomial distributionbinary searchinterpolation searchdata access

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Unnamed Item ⋮ Analysis of recursive batched interpolation search ⋮ Dynamic-window search for real-time simulation of dynamic systems ⋮ Fast search algorithms for look‐up tables ⋮ An adaptation of a root finding method to searching ordered disk files revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Understanding the complexity of interpolation search
• Interpolation search—a log log N search