From: tim_one at email.msn.com (Tim Peters)
Date: Sat, 24 Apr 1999 05:17:10 GMT
Subject: Time complexity of dictionary insertions
In-Reply-To: <glmpv4vnhh6.fsf@caffeine.mitre.org>
References: <glmpv4vnhh6.fsf@caffeine.mitre.org>
Message-ID: <000901be8e11$b4842560$f09e2299@tim>
X-UID: 751                                                  

[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






