[Haskell-cafe] k-minima in Haskell

[ajb at spamcop.net]

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 <igloo at earth.li>:

> 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