A tradeoff between search and update in dictionaries

Abstract

Borodin, Fich, Meyer auf der Heide, Upfal and Wigderson [Theoret. Comput. Sci. 58 (1998) 57-68] showed lower bounds for search time in implicit dictionaries with bounded update time. In particular, their result implies a lower bound of Ω(n^ε) for search time in an implicit dictionary whenever the update time is bounded by a constant. They ask whether a similar result is true for dictionaries with explicit pointers. We answer their question in the affirmative by observing that stronger results follow easily from an earlier result of Borodin, Guibas, Lynch and Yao [Inform. Process. Lett. 12 (1981) 71-75]. In particular, a lower bound of Ω(n) for search time holds whenever the update time is bounded by a constant. Our results hold even if the dictionary uses randomization and the update time is amortized.