The simplest implementation is O(n log(k)) (inserts every element, then drops at most one element).
Caching the k-th best element and only inserting new items has the same worst case behavior in ordered cases. There is a true O(n + k) algorithm based on quicksort (I think). On Mon, Apr 25, 2011 at 2:26 PM, Jake Mannix <[email protected]> wrote: > On Mon, Apr 25, 2011 at 2:23 PM, Jake Mannix <[email protected]> > wrote: > > > > > > This is O(n + k*log(k)) for a randomly sorted list. > > > > This is a bit sloppy: there's a multiplicative factor of log(n) also in the > second > additive factor, but that's still linear overall. > > -jake >
