efficient running median

sturlamolden sturlamolden at yahoo.no
Wed Oct 14 01:20:06 CEST 2009

On 14 Okt, 00:03, Steven D'Aprano
<ste... at REMOVE.THIS.cybersource.com.au> wrote:

> Obviously to run in O(log n) you must have already built the tree.

You don't need a tree. Quickselect is a partial quicksort.

But my memory served me badly, quickselect is O(n).

More information about the Python-list mailing list