Use this resource - and many more! - in *your* textbook!

AcademicPub holds over eight million pieces of educational content for you to mix-and-match *your* way.

**Not an educator**but still interested in using this content? No problem! Visit our provider's page to contact the publisher and get permission directly.

# Static dictionaries on AC/sup 0/ RAMs: query time /spl theta/(/spl radic/log n/log log n) is necessary and sufficient

## By: Riis, S.; Miltersen, P.B.; Andersson, A.; Thorup, M.;

1996 / IEEE / 0-8186-7594-2

### Description

This item was taken from the IEEE Periodical ' Static dictionaries on AC/sup 0/ RAMs: query time /spl theta/(/spl radic/log n/log log n) is necessary and sufficient ' In this paper we consider solutions to the static dictionary problem on AC/sup 0/ RAMs, i.e. random access machines where the only restriction on the finite instruction set is that all computational instructions are in AC/sup 0/. Our main result is a tight upper and lower bound of /spl theta/(/spl radic/log n/log log n) on the time for answering membership queries in a set of size n when reasonable space is used for the data structure storing the set; the upper bound can be obtained using O(n) space, and the lower bound holds even if we allow space 2/sup polylog n/. 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 /spl Omega/(log w/log log to), where w is the word size of the machine (and log the size of the universe). This matches the depth of multiplication and integer division, used in the perfect hashing scheme by M.L. Fredman, J. Komlos and E. Szemeredi (1984).

**Related Topics**

Query Time

Random Access Machines

Finite Instruction Set

Computational Instructions

Membership Queries

Data Structure

Unit-cost Assumption

Constant Query Time Solution

Multiplication

Integer Division

Dictionaries

Circuits

Computer Aided Instruction

Read-write Memory

Costs

Councils

Registers

Robustness

Computational Efficiency

Computational Modeling

Ac/sup 0/ Rams

Static Dictionaries

Perfect Hashing Scheme

Data Structures

Engineering

Upper Bound