# The Randomized Complexity of Maintaining the Minimum

In * Proc. 5th Scandinavian Workshop on Algorithm Theory*, volume 1097 of * Lecture Notes in Computer Science*, pages 4-15. Springer Verlag, Berlin, 1996.

## Abstract

The complexity of maintaining a set under the operations ** Insert**,
** Delete** and ** FindMin** is considered. In the comparison model it
is shown that any randomized algorithm with expected amortized cost
*t* comparisons per ** Insert** and ** Delete** has expected cost at
least *n*/(*e*2^{2t})-1 comparisons for ** FindMin**. If ** FindMin**
is replaced by a weaker operation, ** 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.

**Copyright notice**
© Springer-Verlag Berlin Heidelberg 1996. All rights reserved.

**Online version**

swat96min.pdf (219 Kb)

**DOI**

10.1007/3-540-61422-2_116

**Slides**
swat96min.pdf (99 Kb)

**BIBT**_{E}X entry

@incollection{swat96min,
author = "Gerth St{\o}lting Brodal and Shiva Chaudhuri and Jaikumar Radhakrishnan",
booktitle = "Proc. 5th Scandinavian Workshop on Algorithm Theory",
doi = "10.1007/3-540-61422-2_116",
isbn = "978-3-540-61422-7",
pages = "4-15",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "The Randomized Complexity of Maintaining the Minimum",
volume = "1097",
year = "1996"
}