The Randomized Complexity of Maintaining the Minimum

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

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/(e2^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_EX entry

@incollection{swat96min,
  author = "Gerth Stø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"
}