[Haskell-cafe] Time and space complexity of "take k . sort"
westondan at imageworks.com
Thu Oct 22 16:18:48 EDT 2009
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 <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.
More information about the Haskell-Cafe