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

G'day all. I wrote:

...

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

Quoting Ian Lynagh :

Hmm, is something wrong with the following?: [...] Total: O(n + k log k)

The problem with with my simplifications. :-) But as an exercise, prove: O(n log (n/(n-k)) + k log (n-k)) <= O(n + k log k) Cheers, Andrew Bromage