Time & Space Complexity Reference
There is an open source project that acts as comprehensive cross reference for time and space complexity for Python and the standard library. It was partially inspired by this wiki page.
Python Time & Space Complexity Reference
Time Complexity
This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n).
Generally, 'n' is the number of elements currently in the container. 'k' is either the value of a parameter or the number of elements in the parameter.
list
The Average Case assumes parameters generated uniformly at random.
Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead.
Operation |
Average Case |
|
Copy |
O(n) |
O(n) |
Append[1] |
O(1) |
O(1) |
Pop last |
O(1) |
O(1) |
Pop intermediate[2] |
O(n) |
O(n) |
Insert |
O(n) |
O(n) |
Get Item |
O(1) |
O(1) |
Set Item |
O(1) |
O(1) |
Delete Item |
O(n) |
O(n) |
Iteration |
O(n) |
O(n) |
Get Slice |
O(k) |
O(k) |
Del Slice |
O(n) |
O(n) |
Set Slice |
O(k+n) |
O(k+n) |
Extend[1] |
O(k) |
O(k) |
O(n log n) |
O(n log n) |
|
Multiply |
O(nk) |
O(nk) |
x in s |
O(n) |
|
min(s), max(s) |
O(n) |
|
Get Length |
O(1) |
O(1) |
collections.deque
A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.
Operation |
Average Case |
Amortized Worst Case |
Copy |
O(n) |
O(n) |
append |
O(1) |
O(1) |
appendleft |
O(1) |
O(1) |
pop |
O(1) |
O(1) |
popleft |
O(1) |
O(1) |
extend |
O(k) |
O(k) |
extendleft |
O(k) |
O(k) |
rotate |
O(k) |
O(k) |
remove |
O(n) |
O(n) |
Get Length |
O(1) |
O(1) |
set
See dict -- the implementation is intentionally very similar.
Operation |
Average case |
Worst Case |
notes |
x in s |
O(1) |
O(n) |
|
Union s|t |
|
|
|
Intersection s&t |
O(min(len(s), len(t))) |
O(len(s) * len(t)) |
replace "min" with "max" if t is not a set |
Multiple intersection s1&s2&..&sn |
|
(n-1)*O(l) where l is max(len(s1),..,len(sn)) |
|
Difference s-t |
O(len(s)) |
|
|
s.difference_update(t) |
O(len(t)) |
|