Tables should be sorted (on random access machines)

  • Faith Fich
  • Peter Bro Miltersen

Abstract

We consider the problem of storing an n element subset S of a universe
of size m, so that membership queries (is x in S?) can be answered
efficiently. The model of computation is a random access machine with
the standard instruction set (direct and indirect addressing, conditional
branching, addition, subtraction, and multiplication). We show that if s
memory registers are used to store S, where n <= s <= m/n^epsilon, then query
time  Omega(log n) 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 s <= m/n^epsilon is essentially optimal;
we show that if n + m/n^o(1) registers may be used, query time o(log n) is
possible.
Published
1995-01-26
How to Cite
Fich, F., & Miltersen, P. (1995). Tables should be sorted (on random access machines). BRICS Report Series, 2(26). https://doi.org/10.7146/brics.v2i26.19928