Static Dictionaries on RAMs: Query Time is Necessary and Sufficient
Arne Andersson · Foundations of Computer Science · 1996
In this paper we consider solutions to the static dictionary problem on RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computationalinstructions are in . Our main result is a tight upper and lower bound of on the time for answering membership queries in a set of size when reasonable space is used for the data structure storing the set; the upper bound can be obtained using space, and the lower bound holds even if we allow space . Several variations of this result are also obtained. Among others, we show a tradeoff between time and circuit depth under the unit-cost assumption: any RAM instruction set which permits a linear space, constant query time solution to the static dictionary problem must have an instruction of depth , where is the word size of the machine (and the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by Fredman, Koml´ and Szemer´ edi.