𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Average search and update costs in skip lists

✍ Scribed by Thomas Papadakis; J. Ian Munro; Patricio V. Poblete

Book ID
105430705
Publisher
Springer Netherlands
Year
1992
Tongue
English
Weight
992 KB
Volume
32
Category
Article
ISSN
0006-3835

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A tradeoff between search and update in
A tradeoff between search and update in dictionaries
✍ Jaikumar Radhakrishnan; Venkatesh Raman πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 64 KB

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 up