Python Time Complexity Reference

Abstraction: Big-O complexity of CPython built-in data structure operations

Key points:

• List: O(1) for append, get/set item, get length; O(n) for insert, delete, pop-intermediate, copy, iteration; append is amortized O(1) due to dynamic resizing
• Deque: O(1) for append/appendleft/pop/popleft at both ends; O(n) for remove from middle
• Dict: O(1) average for get/set/delete/lookup; O(n) worst case due to hash collisions; worst-case n is maximum size ever achieved, not current size
• Set difference s-t (O(len(s))) vs s.difference_update(t) (O(len(t))) have different complexities depending on direction; choose based on which set is larger
• Set membership x in s: O(1) average, O(n) worst case; set intersection O(min(len(s),len(t))) average
• Negative list indices in R remove elements; in Python they index from the end — know your language

Connections: Python · Algorithm Complexity · Data Structures

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