A tradeoff between search and update I dictionaries

摘要

Bordoin, Fich, Meyer auf der Heide, Upfal and Wigderson [Theoret. Comput. Soci. 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 form 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 hold whenever the update time is bounded by a constant. Our results hold even if the dictionary uses randomization and the update time is amortized.