A tradeoff between search and update time for the implicit dictionary problem

Borodin, Allan
Fich, Faith E.
Meyer Auf Der Heide, Friedhelm
Upfal, Eli
Wigderson, Avi

Open PDF

Open link

Publication date

June 1988

DOI

10.1016/0304-3975(88)90018-7

Publisher

Published by Elsevier B.V.

ISSN

0304-3975

Citation count (estimate)

Abstract

AbstractThis paper proves a tradeoff between the time it takes to search for elements in an implicit dictionary and the time it takes to update the value of elements in specified locations of the dictionary. It essentially shows that if the update time is constant, then the search time is Ω(nε) for some constant ε>0

Extracted data

We use cookies to provide a better user experience.

Data Protection

A tradeoff between search and update time for the implicit dictionary problem

Abstract

Extracted data

A tradeoff between search and update time for the implicit dictionary problem

Abstract

Extracted data

Related items

Related items