A trade-off for worst-case efficient dictionaries
Rasmus Pagh · 2000
We consider dynamic dictionaries over the universe U = {0, 1}^w on a unit-cost RAM with word size w and a standard instruction set, and present a linear space deterministic dictionary accommodating membership queries in time (log log n)^O(1) and updates in time (log n)^O(1), where n is the size of the set stored. Previous solutions either had query time (log n) 18 or update time 2 !( p log n) in the worst case.