[Haskell-cafe] Re: Time and space complexity of "take k . sort"
apfelmus at quantentunnel.de
Fri Oct 23 04:21:03 EDT 2009
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
> Correction: O(n*log(k))
It's O(n + k log k) (which is the same as O(n + k log n) ):
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) .
More information about the Haskell-Cafe