Sorted dictionary

[Arnaud Delobelle]

"Jan Kaliszewski" <zuo at chopin.edu.pl> writes:

> Dnia 21-01-2010 o 09:27:52 Raymond Hettinger <python at rcn.com> napisał(a):
>
>> On Jan 20, 5:02 pm, "Jan Kaliszewski" <z... at chopin.edu.pl> 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