list

Abstraction: CPython built-in container Big-O operation complexity reference

Key points:

• list: append/get/set O(1); insert/delete/pop-intermediate O(n); sort O(n log n)
• collections.deque: append and pop from both ends O(1); random access is slow
• set/dict: membership test and get/set O(1) average, O(n) worst case due to hash collisions
• dict has a fast-path for str-only keys that reduces constant factors without changing Big-O
• Worst-case dict/set size is the historical max size, not current size (affects Copy and Iteration)
• set difference s-t is O(len(s)); in-place s.difference_update(t) is O(len(t)) — choose based on which is larger

Connections: Python · Cpython · Time Complexity · Data Structures

Source: http://wiki.python.org/moin/TimeComplexity