Time complexity of various iterable operations in Python
List
| Operation |
Average Case |
Operation |
Average Case |
| copy |
O(n) |
arr.append(v) |
O(1) |
| arr.pop(i) |
O(1) |
arr.pop(1) |
O(n) |
| .insert(i, v) |
O(n) |
get |
O(1) |
| set |
O(1) |
arr.remove(v) |
O(n) |
| iteration |
O(n) |
get slice |
O(k) |
| del slice |
O(n) |
set slice |
O(k+n) |
| extend |
O(k) |
arr.sort() |
O(n log n) |
| multiply |
O(nk) |
x in s |
O(n) |
| min(arr)/max(arr) |
O(n) |
len(arr) |
O(1) |
| arr.reverse() |
O(n) |
arr.count(v) |
O(n) |
collections.deque
| Operation |
Average Case |
Operation |
Average Case |
| copy |
O(n) |
append |
O(1) |
| appendleft |
O(1) |
pop |
O(1) |
| popleft |
O(1) |
extend |
O(k) |
| extendleft |
O(k) |
rotate |
O(k) |
| remove |
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 |
| multi 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 differece 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 |
Operation |
Average Case |
| k in d |
O(1) |
copy |
O(n) |
| get item |
O(1) |
set item |
O(1) |
| delete item |
O1() |
iteration |
O(n) |
Referece: https://wiki.python.org/moin/TimeComplexity