How to find the kth smallest element at O(n) if we know there is O(n) function that returns the median of an array

Question

I am trying to find an algorithm that finds kth smallest element from unsorted array of size n at O(n) by using a function that returns the median of array of size n at O(n). I think I have to find a recursive function that has time complexity like cn+cn/2+cn/2^2+....+cn/2^j=O(n).

Answer 1

You can use quickselect, using the provided O(n) median-finding algorithm.

Find the median in O(n) time, separate the array into three parts (smaller, equal and greater than the median), then recurse into the relevant part.

The complexity analysis is easy (compared to the standard randomized Quickselect algorithm). Finding the median and pivoting the array are both O(n), and then the size of array one recurses into has at most n/2 elements (by the definition of median). So the recurrence relation is T(n) = n + T(n/2) for which the solution is T(n) = O(n).