"Jan Kaliszewski" <[email protected]> writes: > Dnia 21-01-2010 o 09:27:52 Raymond Hettinger <[email protected]> napisał(a): > >> On Jan 20, 5:02 pm, "Jan Kaliszewski" <[email protected]> wrote: > >>> http://code.activestate.com/recipes/576998/ > >> Using an underlying list to track sorted items >> means that insertion and deletion take O(n) time. >> That could be reduced to O(log n) time by using >> a blist or skiplist as the underlying structure >> for maintaining a sort. > > Please note that I used funcions from bisect, that use binary search. > > Doesn't it take O(log n) time?
Insertion and deletion are still O(n) as all items to the right of the inserted/deleted one have to be shifted by one place. -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
