# The Randomized Complexity of Maintaining the Minimum

Technical Report, BRICS-RS-96-40, BRICS, Department of Computer Science, Aarhus University, 20 pages, 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 *n*/(*e*2^{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**
Copyright © 1996, BRICS, Department of Computer Science,
Aarhus University. All rights reserved.

**Online version**

brics-rs-96-40.pdf (344 Kb)

**BIBT**_{E}X entry

@techreport{brics-rs-96-40,
author = "Gerth St{\o}lting Brodal and Shiva Chaudhuri and Jaikumar Radhakrishnan",
institution = "BRICS, Department of Computer Science, Aarhus University",
issn = "0909-0878",
month = "November",
number = "BRICS-RS-96-40",
pages = "20",
title = "The Randomized Complexity of Maintaining the Minimum",
year = "1996"
}