What is the run time of the set difference function in Python?

Question

The question explains it, but what is the time complexity of the set difference operation in Python?

EX:

A = set([...])
B = set([...])

print(A.difference(B)) # What is the time complexity of the difference function? 

My intuition tells me O(n) because we can iterate through set A and for each element, see if it's contained in set B in constant time (with a hash function).

Am I right?

(Here is the answer that I came across: https://wiki.python.org/moin/TimeComplexity)

Answer 1

looks that you're right, difference is performed with O(n) complexity in the best cases

But keep in mind that in worst cases (maximizing collisions with hashes) it can raise to O(n**2) (since lookup worst case is O(n): How is set() implemented?, but it seems that you can generally rely on O(1))

As an aside, speed depends on the type of object in the set. Integers hash well (roughly as themselves, with probably some modulo), whereas strings need more CPU.