The Randomized Complexity of Maintaining the Minimum

Forfattere

  • Gerth Stølting Brodal
  • Shiva Chaudhuri
  • Jaikumar Radhakrishnan

DOI:

https://doi.org/10.7146/brics.v3i40.20022

Resumé

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.

Downloads

Publiceret

1996-06-10

Citation/Eksport

Brodal, G. S., Chaudhuri, S., & Radhakrishnan, J. (1996). The Randomized Complexity of Maintaining the Minimum. BRICS Report Series, 3(40). https://doi.org/10.7146/brics.v3i40.20022

Nummer

Nr. 40 (1996): RS-40 The Randomized Complexity of Maintaining the Minimum

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).