The randomized complexity of maintaining the minimum

Brodal, Gerth Stølting ; Chaudhuri, Shiva ; Radhakrishnan, Jaikumar (1996) The randomized complexity of maintaining the minimum Lecture Notes in Computer Science, 1097 . pp. 4-15. ISSN 0302-9743

[img]
Preview
PDF - Author Version
356kB

Official URL: http://www.springerlink.com/index/70629J3M0645202T...

Related URL: http://dx.doi.org/10.1007/3-540-61422-2_116

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, but no deterministic algorithm. Finally, a deterministic algorithm with constant amortized cost per operation for an offline version of the problem is given.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:89524
Deposited On:27 Apr 2012 14:17
Last Modified:19 May 2016 04:03

Repository Staff Only: item control page