[Haskell-cafe] k-minima in Haskell

[ajb at spamcop.net]

G'day all.

Quoting Thomas Hartman <tphyahoo at gmail.com>:

> 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