Should Tables Be Sorted?
Andrew Chi-Chih Yao · Journal of the ACM · 1981
Optmaahty questions are examined m the following information retrieval problem.Given a set S of n keys, store them so that queries of the form, "Is x E S?" can be answered quickly It is shown that m a rather general model including all the commonly used schemes, [lg(n + I)] probes to the table are needed m the worst case, prowded the key space is sufficiently large The effects of smaller key space and arbitrary encoding are also explored KEY WORDS AND PHRASES mformaUon retrieval, lower bound, optmaahty, query, Ramsey's theorem, search strategy, sorted table