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
![]()
|
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