From: ciupke at fzi.de (Oliver Ciupke)
Date: Thu, 22 Apr 1999 15:16:21 +0200
Subject: Time complexity of dictionary insertions
Message-ID: <371F2125.BEC5F892@fzi.de>
X-UID: 1585                                                  

As I understood from the Python documentation, dictionaries are
implemented as
extensible hash tables. What I didn't find either in the references or
in the FAQ is: what is the
actual time complexity for an insertion into a dictionary?

Do the old contents (probably references) have to be copied when
extending (doubling?) the
dictionary?

I guess updates and deletions have constand complexity, right?

If the complexity of insertion is something like n*log(n), does anyone
know measurements "how
linear" the real measured times are?


Thanks in advance
--Oliver







