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 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.
Step by Step Solution
3.54 Rating (154 Votes )
There are 3 Steps involved in it
The detailed answer for the above question is provided below Let A be an array of n elements and let ... View full answer
Get step-by-step solutions from verified subject matter experts
