[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) ):


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 mailing list