Title :
Dynamic perfect hashing: upper and lower bounds
Author :
Dietzfelbinger, M. ; Karlin, A. ; Mehlhorn, K. ; Der Heide, R. Meyer auf ; Rohnert, H. ; Tarjan, R.E.
Author_Institution :
Dortmund Univ., West Germany
Abstract :
A randomized algorithm is given for the dictionary problem with O(1) worst-case time for lookup and O(1) amortized expected time for insertion and deletion. An Ω(log n) lower bound is proved for the amortized worst-case time complexity of any deterministic algorithm in a class of algorithms encompassing realistic hashing-based schemes. If the worst-case lookup time is restricted to k, then the lower bound for insertion becomes Ω(kn1k/)
Keywords :
computational complexity; file organisation; amortized expected time; amortized worst-case time complexity; deletion; deterministic algorithm; dictionary problem; dynamic perfect hashing; insertion; lookup; lower bounds; randomized algorithm; upper bounds; worst-case time; Algorithm design and analysis; Computational modeling; Contracts; Costs; Data structures; Dictionaries;
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
DOI :
10.1109/SFCS.1988.21968
