The Randomized Complexity of Maintaining the Minimum

Gerth Stølting Brodal, Shiva Chaudhuri, and Jaikumar Radhakrishnan

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/(e22t)-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)

BIBTEX 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"
}