Big-O#
Common-operation complexities for built-in containers (CPython implementation).
Op |
|
|
|
|
|---|---|---|---|---|
Index / get |
O(1) |
O(n) |
O(1) avg |
O(1) (peek) |
Append |
O(1) amort |
O(1) |
O(1) avg |
O(log n) push |
Prepend |
O(n) |
O(1) |
n/a |
n/a |
Pop end |
O(1) |
O(1) |
O(1) avg (popitem) |
O(log n) pop |
Pop front |
O(n) |
O(1) |
n/a |
n/a |
Membership |
O(n) |
O(n) |
O(1) avg |
n/a |
Sort |
O(n log n) |
n/a |
n/a |
O(n) heapify |
References#
Data Structures for the containers themselves.
Time complexity wiki — CPython container performance.