The order statistics problem is to find the ith smallest of n elements for any i. The
Fantastic news! We've Found the answer you've been seeking!
Question:
The order statistics problem is to find the ith smallest of n elements for any i. The median finding problem is a special case of the order statistics problem when i = n/2 or (n+1)/2. Show that any fast algorithm for the median finding problem can actually lead to a fast algorithm for the order statistics problem. In particular, show that if there is an algorithm which can find the median in time c*n, then there must be an algorithm which, for any i, can find the ith smallest element in time 2(c+d)*n, where d*n is the time to partition n elements given any pivot element.
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Posted Date: