The Randomized Complexity of Maintaining the Minimum

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

In Nordic Journal of Computing, Selected Papers of the 5th Scandinavian Workshop on Algorithm Theory (SWAT'96), volume 3(4), pages 337-351, 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; in contrast, it is shown that no deterministic algorithm can have constant cost per operation. Finally, a deterministic algorithm with constant amortized cost per operation for an offline version of the problem is given.

Copyright notice

© 1996 Publishing Association Nordic Journal of Computing, Helsinki.

Online version

njc.swat96.pdf (279 Kb)

BIBT_EX entry

@article{njc.swat96,
  author = "Gerth Stølting Brodal and Shiva Chaudhuri and Jaikumar Radhakrishnan",
  issn = "1236-6064",
  journal = "Nordic Journal of Computing, Selected Papers of the 5th Scandinavian Workshop on Algorithm Theory (SWAT'96)",
  number = "4",
  pages = "337-351",
  title = "The Randomized Complexity of Maintaining the Minimum",
  volume = "3",
  year = "1996"
}

---

Other versions

• The Randomized Complexity of Maintaining the Minimum.
  Gerth Stølting Brodal, Shiva Chaudhuri, and Jaikumar Radhakrishnan.
  Technical Report, BRICS-RS-96-40, BRICS, Department of Computer Science, Aarhus University, 20 pages, November 1996.
• 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.
• 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. [10.1007/3-540-61422-2_116]