Defensive programming

Anders J. Munch andersjm at dancontrol.dk
Mon Jun 2 10:19:34 CEST 2003


"Tim Peters" <tim.one at comcast.net> wrote:
> Sure.  All dict implementations (hash tables) have O(N**2) worst-case
> behavior, over a sequence of N inserts and/or lookups, provoked by a
> sufficiently nasty set of N keys.

A hash table with balanced binary tree collision resolution has 
O(N logN) worst case.  Not that I see any way of using that for Python
dicts.

- Anders






More information about the Python-list mailing list