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 <[EMAIL PROTECTED]>: > 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 _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
