Report Number: CS-TR-79-753
Institution: Stanford University, Department of Computer Science
Title: Should tables by sorted?
Author: Yao, Andrew Chi-Chih
Date: July 1979
Abstract: We examine optimality questions in the following information
retrieval problem: Given a set S of n keys, store them so
that queries of the form "Is x $\in$ S?" can be answered
quickly. It is shown that, in a rather general model
including al1 the commonly-used schemes, $\lceil$ lg(n+l)
$\rceil$ probes to the table are needed in the worst case,
provided the key space is sufficiently large. The effects of
smaller key space and arbitrary encoding are also explored.