finding items that occur more than once in a list

[Hrvoje Niksic]

Ninereeds <stephenhorne100 at aol.com> writes:

> As for the growth pattern, each time you grow the table you have to
> redistribute all the items previously inserted to new locations.
> Resizes would get rarer as more items are added due to the
> exponential growth, but every table resize would take longer too
> since there are more items to move. Inserting n items still
> intuitively looks like O(n^2) to me.
>
> That said, it does remind me of that old exponential realloc trick
> for array resizing. Same thing, I suppose, since a hash table is
> basically an array. Maybe my math "intuition" is just wrong.

That's it.  While table resizes grow linearly in complexity, they
become geometrically rarer.  This is exactly what happens when
resizing dynamic arrays such as Python lists.  Applying your
intuition, appending n elements to a Python list would also have
O(n^2) complexity, which it doesn't.  See, for example,
http://en.wikipedia.org/wiki/Dynamic_array#Geometric_expansion_and_amortized_cost