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.
-
- 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
BibTeX
@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},
}