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

[Heinrich Apfelmus]

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