CODEWITHSUNDEEP
python
SuperString
SuperString

Reputation: 22519

set() runtime in python

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!

Upvotes: 7

Views: 4370

Answers (1)

gnud
gnud

Reputation: 78518

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.

Upvotes: 12

Related Questions