The kth quantiles of an n-element set are the − 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an ( log ) time algorithm to list the kth quantiles of a set.
1. If k=1 we return an empty list.
2. If k is even, we find the median, partition around it, solve two similar subproblems of size ⌊n/2⌋ and return their solutions plus the median.
3. If k is odd, we find the ⌊k/2⌋ and ⌈k/2⌉ boundaries and then we reduce to two subproblems, each with size less than n/2. The worst-case recurrence is:
T(n, k) = 2T(⌊n/2⌋,k/2)+O(n)
Which is the desired bound ­ O(nlgk).
This works easily when the number of elements is ak+k−1 for a positive integer a. When they are a different number, some care with rounding needs to be taken in order to avoid creating two segments that differ by more than 1.