The sets set
are not "sequences" - neither in the internal organization of the data, nor in the interface they implement, since they do not guarantee any order.
Sets actually have the implementation similar to dictionaries - but only the key side: internally, a data structure containing the hash
of objects is used, and this maps to a real reference to the object. So, the "thick" of the search is the hash of the object in that structure.
And, hash searches are rightly made to be O(1).
If the hash is found, the object reference is retrieved - if it is the same object (id’s are the same), the match is given, otherwise an equality comparison is made. These other checks, and even in the case of hash collision, when a sequential search is made between objects of the same hash, do not count for algorithmic complexity.
Of course, the limitation is that "unhashable" objects (in general, mutable objects), cannot be placed in sets (sets), just as they cannot be dictionary keys. If this is necessary, it is necessary to implement a class that responds to the same set interface(see collections.abc
), but with other internal algorithms, which can hardly be O(1), unless they use a similar technique.
Related: Definition of the "Big O" notation
– Homer Simpson