[Haskell-cafe] Re: Time and space complexity of "take k . sort"
Heinrich Apfelmus
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
>> O(n*k*log(k)).
>>
> Correction: O(n*log(k))
It's O(n + k log k) (which is the same as O(n + k log n) ):
http://apfelmus.nfshost.com/quicksearch.html
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) .
Regards,
apfelmus
--
http://apfelmus.nfshost.com
More information about the Haskell-Cafe
mailing list