BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-753
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Should tables by sorted?
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: July 1979
       PAGES:: 38
    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.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-753