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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/79/753/CS-TR-79-753.pdf