Set type in Python is basically implemented as a HashTable.

There're so many great answers above, I'm just gonna state a point that is missing:

I think one more thing is that the size of hashtable is predefined, and adding elements beyond the current capacity triggers a resize of the hash table.

For the complexity part (HashTable):

Amortized:

O(1) for individual additions because resizing is not as often.

Worst case:

O(n) resizing involves rehashing all elements into a larger table, which is a linear operation.