@article{Brodal_Chaudhuri_Radhakrishnan_1996, title={The Randomized Complexity of Maintaining the Minimum}, volume={3}, url={https://tidsskrift.dk/brics/article/view/20022}, DOI={10.7146/brics.v3i40.20022}, abstractNote={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.<br />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<br />per operation. Finally, a deterministic algorithm with constant amortized cost per operation for an offline version of the problem is given.}, number={40}, journal={BRICS Report Series}, author={Brodal, Gerth Stølting and Chaudhuri, Shiva and Radhakrishnan, Jaikumar}, year={1996}, month={Jun.} }