From: tseaver at palladion.com (Tres Seaver)
Date: Fri, 23 Apr 1999 08:05:09 -0500
Subject: Time complexity of dictionary insertions
References: <371F2125.BEC5F892@fzi.de> <7fo08u$4j2$1@nnrp1.dejanews.com>
Message-ID: <37207005.1CC60E1B@palladion.com>
X-UID: 935                                                  

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




