MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 1. by Individual

MPI-I-96-1-014

The randomized complexity of maintaining the minimum

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

May 1996, 12 pages.

.
Status: available - back from printing

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.

  • MPI-I-96-1-014.psMPI-I-96-1-014.pdf
  • Attachement: MPI-I-96-1-014.ps (140 KBytes); MPI-I-96-1-014.pdf (212 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1996-1-014

Hide details for BibTeXBibTeX
@TECHREPORT{BrodalChaudhuriRadhakrishnan96,
  AUTHOR = {Brodal, Gerth Stølting and Chaudhuri, Shiva and Radhakrishnan, Jaikumar},
  TITLE = {The randomized complexity of maintaining the minimum},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-014},
  MONTH = {May},
  YEAR = {1996},
  ISSN = {0946-011X},
}