The Randomized Complexity of Maintaining the Minimum
Gerth Stølting Brodal 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
Available as PostScript, PDF, DVI. |