Just wondering what the run time of lookup for set() is? O(1) or O(n)?
if I have
x = set() whats the runtime of
if "a" in x: print a in set!
+3
A:
set is implemented using a hash, so the lookup is, on average, close to O(1). The worst case is O(n), where n objects have colliding hashes.
gnud
2010-03-04 16:48:52
I found a reference: http://wiki.python.org/moin/TimeComplexity
Fred Larson
2010-03-04 17:11:37
Note that the hash functions and collision resolution algorithm are chosen to make the O(n) case much less threatening than it sounds.
Mike Graham
2010-03-04 17:17:30