In Nordic Journal of Computing, Selected Papers of the 5th Scandinavian Workshop on Algorithm Theory (SWAT'96), volume 3(4), pages 337-351, 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 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.
Copyright notice© 1996 Publishing Association Nordic Journal of Computing, Helsinki.
Online version
njc.swat96.pdf (279 Kb)
BIBT_{E}X entry
@article{njc.swat96, author = "Gerth St{\o}lting Brodal and Shiva Chaudhuri and Jaikumar Radhakrishnan", issn = "1236-6064", journal = "Nordic Journal of Computing, Selected Papers of the 5th Scandinavian Workshop on Algorithm Theory (SWAT'96)", number = "4", pages = "337-351", title = "The Randomized Complexity of Maintaining the Minimum", volume = "3", year = "1996" }
Other versions