# Item

ITEM ACTIONSEXPORT

Released

Report

#### The randomized complexity of maintaining the minimum

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

1996-1-014

(Any fulltext), 11KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Brodal, G. S., Chaudhuri, S., & Radhakrishnan, J.(1996). *The
randomized complexity of maintaining the minimum* (MPI-I-1996-1-014). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-A18C-7

##### Abstract

The complexity of maintaining a set under the operations {\sf Insert}, {\sf Delete} and {\sf FindMin} is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost $t$ comparisons per {\sf Insert} and {\sf Delete} has expected cost at least $n/(e2^{2t})-1$ comparisons for {\sf FindMin}. If {\sf FindMin} 474 is replaced by a weaker operation, {\sf FindAny}, then it is shown that a randomized algorithm with constant expected cost per operation exists, but no deterministic algorithm. Finally, a deterministic algorithm with constant amortized cost per operation for an offline version of the problem is given.