A hybrid algorithm for finding the kth smallest of n elements in O(n) time

0.00 Avg rating—0 Votes

Article ID:	iaor1988179
Country:	Switzerland
Volume:	13
Start Page Number:	401
End Page Number:	419
Publication Date:	Nov 1988
Journal:	Annals of Operations Research
Authors:	Fischetti Matteo, Martello Silvano
Keywords:	computational analysis

Abstract:

The problem of finding the kth smallest of n elements can be solved either with O(n) algorithms or with O(n²) algorithms. Although they require a higher number of operations in the worst case, O(n²) algorithms are generally preferred to O(n) algorithms because of their better average performance. The authors present a hybrid algorithm which is O(n) in the worst case and efficient in the average case.

Reviews

Required fields are marked *. Your email address will not be published.