The Randomized Complexity of Maintaining the Minimum

Gerth Stølting Brodal
Shiva Chaudhuri
Jaikumar Radhakrishnan

November 1996


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 tex2html_wrap_inline30 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.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.