Re: [Haskell-cafe] k-minima in Haskell

On Fri, Apr 13, 2007 at 07:32:20AM -0400, ajb@spamcop.net wrote:

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).

Hmm, is something wrong with the following?: Tuple each element with its position: O(n) Find kth smallest element in linear time, as per [1]: O(n) Filter list for elements <= kth smallest: O(n) Sort filtered list by position: O(k log k) map snd to get the positions: O(k) Total: O(n + k log k) (the filter step will take care of elements with the same value as the kth smallest, as the filter is also comparing element positions when the values are the same). Thanks Ian [1] http://en.wikipedia.org/wiki/Selection_algorithm