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
