AbstractThe 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/(e22t)-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.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Selected references
- Christos Levcopoulos and Mark H. Overmars. A balanced search tree with O(1) worst-case update time. Acta Informatica, 26(3):269-277, 1988.
- Colin McDiarmid. Average-case lower bounds for searching. SIAM Journal on Computing, 17(5):1044-1060, October 1988.
- Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, pages 222-227, Providence, Rhode Island, 31 October-2 November 1977. IEEE.