Efficiency of a Binary Comparison Storage Technique
- 1 July 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 21 (3), 376-384
- https://doi.org/10.1145/321832.321836
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 .Keywords
This publication has 2 references indexed in Scilit:
- Optimizing binary trees grown with a sorting algorithmCommunications of the ACM, 1972
- Some Combinatorial Properties of Certain Trees With Applications to Searching and SortingJournal of the ACM, 1962