python 2.7 set and list remove time complexity

Question

Wondering the time complexity of remove of list, and remove of set.

My thought and study result is,

1. Removal of list is O(n)
2. Removal of set is O(1).

I just studied some discussion, but never prove it. If anyone could shed some lights, it will be great. Especially how set implements with O(1) removal?

Using Python 2.7.

a = set([1,2,3,4,5])
b = [1,2,3,4,5]

a.remove(3)
b.remove(3)

print a
print b

Answer 1

From the docs:

list.remove(x) Remove the first item from the list whose value is x. It is an error if there is no such item.

Without going into the details of the implementation, the item to remove can be anywhere in the list. A linear scan time is necessary in order to find the item before it can be removed. Once you find the index of the item to remove, you need to shift all the elements down by one index. In any case there's index amount of traversal and size - index amount of shifting involved. Therefore the removal time is equivalent to traversing the entire list: O(n).

You can find the source here: https://hg.python.org/cpython/file/tip/Objects/listobject.c#l2197 (also look for list_ass_slice(..)).

---

However, a set is different. It uses the hash value of the object being stored to locate it in its buckets. On an average, locating of objects using hash value is almost constant time. Note that it might not always be constant time where there's hash collision and a further search is required. But assuming a good hash function, it usually is.

UPDATE: I must thank Stefan Pochmann for pointing out the mistake.