Time complexity of dictionary insertions

[Tim Peters]

[someone asks about the time complexity of Python dict insertions]

[Tim replies]
> Min O(1), Max O(N), Ave O(1).  If the hash function is doing
> a terrible job (e.g. maps every key to the same hash value), make
> those all O(N).

[one person confuses the issue]
> C++ STL junkies know this as "amortized constant time".

[and another compounds it]
> So does anyone who has ever studied much at all about algorithms, data
> structures, and optimization.
>
> It's not a C++ thing.  It's a computer science thing.

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.

reassuringly y'rs  - tim