Paul Johnson wrote: > Paul Johnson wrote: >> >> > takeLargest k = take k . sort >> >> Because "sort" is lazily evaluated this only does enough sorting to >> find the first k elements. I guess the complexity is something like >> O(n*k*log(k)). >> > Correction: O(n*log(k))
It's O(n + k log k) (which is the same as O(n + k log n) ): http://apfelmus.nfshost.com/quicksearch.html The remark about O(k) space complexity of the other algorithm is interesting, since this means that it's not even allowed to copy its argument of size O(n) . Regards, apfelmus -- http://apfelmus.nfshost.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe