--- Comment #9 from Christopher Schultz <> ---
Getting down to algorithmic complexity, the TimSort is O(n log n) -- same as
merge sort. But again, we don't actually need a completely-sorted array. We
just need the oldest N items.

If you do a single scan of the array, that O(n) of course, so N scans of the
array will be N * O(n). Note N != n. N is the number of evictions you want to
do, and "n" is the number of elements in the list.

sort+evict = O(n log n)
multiple scans = N * O(n)

Given that N should be relatively small, I think multiple scans wins the
complexity battle.

You are receiving this mail because:
You are the assignee for the bug.
To unsubscribe, e-mail:
For additional commands, e-mail:

Reply via email to