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

BIBTEX entry

@article{njc.swat96,
  author = "Gerth St{\o}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