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


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)
Issue number3
StatePublished - Jul 1 1974


  • 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


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

Cite this