Efficiency of a Binary Comparison Storage Technique

E. M. Palmer, M. A. Rahimi, R. W. Robinson*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The efficiency of an information storage technique based on binary comparisons is analyzed. Generating functions are applied to finding the mean and variance of the number of comparisons needed to retrieve one item from a store of n items. Surprisingly, the variance approaches 7 - 2/3π2 for large n.

Original languageEnglish (US)
Pages (from-to)376-384
Number of pages9
JournalJournal of the ACM (JACM)
Volume21
Issue number3
DOIs
StatePublished - Jul 1 1974

Keywords

  • binary trees
  • directory search
  • generating functions
  • information retrieval
  • mean
  • searching
  • trees
  • variance

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Efficiency of a Binary Comparison Storage Technique'. Together they form a unique fingerprint.

Cite this