From: justin at linus.mitre.org (Justin Sheehy)
Date: 23 Apr 1999 17:40:21 -0400
Subject: Time complexity of dictionary insertions
References: <371F2125.BEC5F892@fzi.de> <7fo08u$4j2$1@nnrp1.dejanews.com> <37207005.1CC60E1B@palladion.com>
Message-ID: <glmpv4vnhh6.fsf@caffeine.mitre.org>
X-UID: 1493                                                  

Tres Seaver <tseaver at palladion.com> writes:

> > 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".

So does anyone who has ever studied much at all about algorithms, data 
structures, and optimization.

It's not a C++ thing.  It's a computer science thing.

-Justin





