[Haskell-cafe] Re: Time and space complexity of "take k . sort"

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