Python enable us to perform advanced operation in very expressive way, meanwhile covers many users’ eyes from underlying implement details. If the performance of your application plays a critical role, please always keep in mind the time complexity of these common operations.
The following table is an important cheat sheet to memorize to keep your applications behave.
Python official page
List
| Operation |
Average Case |
Amortized Worst Case |
| Copy |
O(n) |
O(n) |
| Append |
O(1) |
O(1) |
| 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 |
O(k) |
O(k) |
| Sort |
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
| 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) |
set
| Operation |
Average case |
Worst Case |
notes |
| x in s |
O(1) |
O(n) |
|
| Union s |
t |
O(len(s)+len(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)) |
|
| Symmetric Difference s^t |
O(len(s)) |
O(len(s) * len(t)) |
|
| s.symmetric_difference_update(t) |
O(len(t)) |
O(len(t) * len(s)) |
|
dict
| Operation |
Average Case |
Amortized Worst Case |
| Copy |
O(n) |
O(n) |
| Get Item |
O(1) |
O(n) |
| Set Item |
O(1) |
O(n) |
| Delete Item |
O(1) |
O(n) |
| Iteration |
O(n) |
O(n) |