[Haskell-cafe] Time and space complexity of "take k . sort"
ketil at malde.org
Thu Oct 22 15:45:54 EDT 2009
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.
If I haven't seen further, it is by standing in the footprints of giants
More information about the Haskell-Cafe