^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} unknown^{4} Department of Computer Science, Science and Technology, Aarhus University

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

Type:

Conference paper

Language:

English

Published in:

Nordic Journal of Computing, 1996, Vol 3, Issue 4, p. 337-351

Main Research Area:

Science/technology

Publication Status:

Published

Review type:

Peer Review

Conference:

5th Scandinavian Workshop on Algorithm Theory. SWAT '96, 1996