From: moshez at math.huji.ac.il (Moshe Zadka)
Date: Mon, 26 Apr 1999 01:17:48 +0300
Subject: Time complexity of dictionary insertions
In-Reply-To: <000901be8e11$b4842560$f09e2299@tim>
References: <glmpv4vnhh6.fsf@caffeine.mitre.org> <000901be8e11$b4842560$f09e2299@tim>
Message-ID: <Pine.SUN.3.95-heb-2.07.990426011503.1244D-100000@sunset.ma.huji.ac.il>
X-UID: 64                                                  

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.





