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

Dan Weston 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.
> -k

More information about the Haskell-Cafe mailing list