Python Hardware Complexity Reference
Big-O & Memory Complexity Cheatsheet
Time and space complexity lookup matrix for Python built-in data structure operations with underlying CPython explanations.
| Data Structure | Operation | Time Complexity | Space Complexity | WHY Under The Hood |
|---|---|---|---|---|
| List | arr[i] (Indexing) | O(1) | O(1) | Direct memory pointer calculation: Base + (i * 8 bytes) |
| List | arr.append(x) | O(1) Amortized | O(1) | Over-allocates memory slots using (N >> 3) formula |
| List | arr.insert(0, x) | O(N) | O(1) | Shifts all N existing elements 1 slot right in memory |
| List | arr.pop(0) | O(N) | O(1) | Shifts all N-1 remaining elements 1 slot left in memory |
| List | x in arr (Search) | O(N) | O(1) | Unindexed linear memory sweep item by item |
| Set | x in set (Search) | O(1) Amortized | O(N) | Computes hash(x) & mask to jump straight to hash bucket |
| Set | set.add(x) | O(1) Amortized | O(1) | Places pointer reference directly in hash bucket index |
| Dict | dict[key] (Lookup) | O(1) Amortized | O(N) | PyDictObject sparse index table offset jump |
| Deque | deque.popleft() | O(1) | O(1) | Doubly-linked 62-element block ring node pointer update |
| Built-in | sorted(arr) | O(N log N) | O(N) | Timsort algorithm leveraging contiguous run runs |