Time complexity of dictionary insertions

[Tres Seaver]

tim_one at email.msn.com wrote:
> 
> In article <371F2125.BEC5F892 at fzi.de>,
>   Oliver Ciupke <ciupke at fzi.de> wrote:
> > As I understood from the Python documentation, dictionaries are
> > implemented as extensible hash tables.
> 
> Yes.
> 
> > 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?
> 
> 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).

C++ STL junkies know this as "amortized constant time".

=========================================================
Tres Seaver         tseaver at palladion.com    713-523-6582
Palladion Software  http://www.palladion.com