The kth quantiles of an n-element set are the k - 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the kth quantiles of a set.
The straight forward solution would be to select every k, 2k, 3k .. ik the smallest element, whose running time is O(kn) (k calls to select procedure of O(n)). But this can be optimized to do better than O(kn). After finding the median of medians at the index 'i' in the select procedure, we make the following recursive call.
if the index of the median of medians i is > k, recursively call select the kth smallest element in the left subarray A[0 ... i]
if the i is < k, recursively select the n - i + k th smallest element in the right subarray A[i+1 ... n].
Can the above recursive calls be modified as below which would reduce the factor 'k' to 'log k' ?
if the index of the median of medians i is > k, recursively select the kth smallest element in the left subarray A[0 ... i] and also recursively select the n - k th smallest element in the right subarray A[i+1 ... n].
if the i is < k, recursively select the n - i + k th smallest element in the right subarray A[i+1 ... n] and also recursively select k th smallest element in the left subarray A[0 ... i].
The main call would be just select(A, k, n).