[Haskell-cafe] k-minima in Haskell
ajb at spamcop.net
ajb at spamcop.net
Sun Apr 15 01:57:22 EDT 2007
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
More information about the Haskell-Cafe
mailing list