[Python-ideas] set.add() return value
Chris Rebert
pyideas at rebertia.com
Fri Feb 13 00:12:37 CET 2009
On Thu, Feb 12, 2009 at 2:59 PM, Ralf W. Grosse-Kunstleve
<rwgk at yahoo.com> wrote:
>
>> * insertion and lookup times are O(1), not O(n log n).
>
>
> Sorry, I was thinking the .add() is happening inside a loop with N iterations,
> with N also being the eventual size of the set. Is O(N log N) correct then?
>
> http://en.wikipedia.org/wiki/Big_O_notation says:
>
> O(log N) example: finding an item in a sorted array with a binary search.
>
> Isn't that what set is doing?
Python's set uses an unsorted hash table internally and is thus O(1), not O(N).
Cheers,
Chris
--
Follow the path of the Iguana...
http://rebertia.com
More information about the Python-ideas
mailing list