Time complexity of dictionary insertions

[Moshe Zadka]

On Sat, 24 Apr 1999, Tim Peters wrote:

> [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).

<snipped discussion whether Amortized Constant Time is a C++/STL/CS
concept>

> 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 is interesting. What is the WCS behaviour of Python dicts?

but-it-doesn't-really-matter-'cause-it-takes-finite-time-anyway-ly y'rs,
Z.

--
Moshe Zadka <mzadka at geocities.com>. 
QOTD: What fun to me! I'm not signing permanent.