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

[Ketil Malde]

Paul Johnson <paul at cogito.org.uk> 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
-- 
If I haven't seen further, it is by standing in the footprints of giants