Time complexity of dictionary insertions
Moshe Zadka
moshez at math.huji.ac.il
Sun Apr 25 18:17:48 EDT 1999
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.
More information about the Python-list
mailing list