# The Randomized Complexity of Maintaining the Minimum

Technical Report, MPI-I-96-1-014, Max-Planck-Institut für Informatik, May 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.

**Online version**
mpi-i-96-1-014.pdf (237 Kb)

**BIBT**_{E}X entry

@techreport{mpi-i-96-1-014,
author = "Gerth St{\o}lting Brodal and Shiva Chaudhuri and Jaikumar Radhakrishnan",
institution = "Max-Planck-Institut f{\"u}r Informatik",
month = "May",
number = "MPI-I-96-1-014",
title = "The Randomized Complexity of Maintaining the Minimum",
year = "1996"
}