Tables should be sorted
(on random access machines)

Faith Fich
Peter Bro Miltersen

May 1995


We consider the problem of storing an n element subset S of a universe of size m, so that membership queries (is tex2html_wrap_inline26 ) can be answered efficiently. The model of computation is a random access machine with the standard instruction set (direct and indirect adressing, conditional branching, addition, subtraction, and multiplication). We show that if s memory registers are used to store S, where tex2html_wrap_inline32 , then query time tex2html_wrap_inline34 is necessary in the worst case. That is, under these conditions, the solution consisting of storing S as a sorted table and doing binary search is optimal. The condition tex2html_wrap_inline38 is essentially optimal; we show that if tex2html_wrap_inline40 registers may be used, query time tex2html_wrap_inline42 is possible.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.