Abstract:
We consider the problem of storing an n element subset S of
a universe of size m, so that membership queries (is 
) 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 
,
then query time 
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 
is essentially optimal; we show that if 
registers may be
used, query time 
is possible.
Available as PostScript, PDF, DVI.