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.

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

Copyright © 1996, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-96-40.pdf (344 Kb)

BIBTEX entry

@techreport{brics-rs-96-40,
  author = "Gerth St{\o}lting Brodal and Shiva Chaudhuri and Jaikumar Radhakrishnan",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "November",
  number = "BRICS-RS-96-40",
  pages = "20",
  title = "The Randomized Complexity of Maintaining the Minimum",
  year = "1996"
}