The Randomized Complexity of Maintaining the Minimum

  • Gerth Stølting Brodal
  • Shiva Chaudhuri
  • Jaikumar Radhakrishnan

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.
Published
1996-06-10
How to Cite
Brodal, G., Chaudhuri, S., & Radhakrishnan, J. (1996). The Randomized Complexity of Maintaining the Minimum. BRICS Report Series, 3(40). https://doi.org/10.7146/brics.v3i40.20022