Time complexity of dictionary insertions

Daniel Smart cppdan at dansmart.com
Sat Apr 24 01:38:50 EDT 1999


[posted and mailed]

Tim Peters <tim_one at email.msn.com> wrote in 
<000901be8e11$b4842560$f09e2299 at tim>:

>[someone asks about the time complexity of Python dict insertions]
>
>[Tim replies]
>[one person confuses the issue]
>[and another compounds it]
>This one-ups-man-ship would be a lot cuter if Python's dict insertion
>were in fact amortized constant time <0.9 wink>.  It's not, and the
>answer I gave doesn't imply that it is.  Insertion in STL hashed
>associative containers isn't ACT either.
>
This attempt at one-ups-man-ship would be a lot cuter if the STL had any 
kind of hashed containers, associative or otherwise, whose performance 
could be quoted! <tentative wink>

>reassuringly y'rs  - tim

Argumentatively y'rs - dan.

-- 
Dan Smart. C++ Programming and Mentoring.
cppdan at dansmart.com




More information about the Python-list mailing list