Time complexity of dictionary insertions
Justin Sheehy
justin at linus.mitre.org
Fri Apr 23 17:40:21 EDT 1999
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
More information about the Python-list
mailing list