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

Unless of course you use a GHC RULE to rewrite the RHS into the LHS, which should always be a valid transformation. Ketil Malde wrote:

Paul Johnson writes:

...

...

takeLargest k = take k . sort

...

But of equal practical interest is the space complexity. The optimum algorithm is to take the first k items, sort them, and then iterate through the remaining items by adding each item to the sorted list and then throwing out the highest one. That has space complexity O(k). What does the function above do?

Well - 'sort' doesn't know the value of 'k', so it needs to retain all elements, just in case 'k' might be 'n'. So I don't see how you can use space less than 'n' for a construct like the above.

-k