1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University3 unknown4 Department of Computer Science, Science and Technology, Aarhus University
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/(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.
Nordic Journal of Computing, 1996, Vol 3, Issue 4, p. 337-351
Main Research Area:
5th Scandinavian Workshop on Algorithm Theory. SWAT '96, 1996