G'day all.
Quoting Thomas Hartman
Does that mean you can have the k minima in O(n) time, where n is length of list, which would seem to be an improvement?
It's worth considering what the theoretical minimum is. You have n elements, and you need to locate a specific k-element permutation. There are n! / (n-k)! such permutations. You therefore need log(n! / (n-k)!) bits of information. A binary comparison provides one bit of information. So the number of comparisons that you need to get that much information is: O(log(n! / (n-k)!)) = O(n log n - (n-k) log (n-k)) = O(n log (n/(n-k)) + k log (n-k)) That looks right to me. If k << n, then this simplifies to O(n + k log n), and if k is close to n, it simplifies to O(n log n + k). Cheers, Andrew Bromage