Python
Data Types
| category | types |
|---|---|
| text | str |
| numeric | int, float, complex |
| sequence | list, tuple, range |
| mapping | dict |
| set | set, frozenset |
| boolean | bool |
| binary | bytes, bytearray, memoryview |
| none | NoneType |
Time Complexities 1
lists
| operation | time complexity |
|---|---|
sequence.append(item) |
$\mathcal{O}(1)$ |
sequence.pop(item) |
$\mathcal{O}(1)$ |
sequence.insert(0,item) |
$\mathcal{O}(n)$ |
sequence.pop(item,0)
𐃏
|
$\mathcal{O}(n)$ |
sequence[index] |
$\mathcal{O}(1)$ |
sequence[index]=value |
$\mathcal{O}(1)$ |
item in sequence |
$\mathcal{O}(n)$ |
len(sequence) |
$\mathcal{O}(1)$ |
sequence.extend(iterable) |
$\mathcal{O}(k)$ |
sequence + other_sequence |
$\mathcal{O}(n+k)$ |
sequence[index:index+k] |
$\mathcal{O}(k)$ |
sequence.index(item) |
$\mathcal{O}(n)$ |
sequence.count(item) |
$\mathcal{O}(n)$ |
for item in sequence: |
$\mathcal{O}(n)$ |
double-ended queue (deque)
| operation | description | time complexity |
|---|---|---|
queue.append(item) |
Add item to right end | $\mathcal{O}(1)$ |
queue.appendleft(item) |
Add item to left end | $\mathcal{O}(1)$ |
queue.pop() |
Remove and return item from right end | $\mathcal{O}(1)$ |
queue.popleft() |
Remove and return item from left end | $\mathcal{O}(1)$ |
queue.extend(iterable) |
Add all elements from iterable to right end | $\mathcal{O}(k)$ |
queue.extendleft(iterable) |
Add all elements from iterable to left (reversed) | $\mathcal{O}(k)$ |
queue.remove(value) |
Remove first occurrence of value | $\mathcal{O}(n)$ |
queue.rotate(n) |
Rotate n steps right (negative for left) | $\mathcal{O}(k)$ |
queue.clear() |
Remove all elements | $\mathcal{O}(n)$ |
queue.count(value) |
Count occurrences of value | $\mathcal{O}(n)$ |
queue.index(value) |
Find index of first occurrence of value | $\mathcal{O}(n)$ |
queue.reverse() |
Reverse elements in place | $\mathcal{O}(n)$ |
item in queue |
Check if item exists in queue | $\mathcal{O}(n)$ |
queue[0] or queue[-1] |
Access first or last element | $\mathcal{O}(1)$ |
queue[i] |
Access element at index i | $\mathcal{O}(n)$ |
for item in queue |
Iterate through all elements | $\mathcal{O}(n)$ |
dictionary
| operation | time complexity |
|---|---|
mapping[key]=value |
$\mathcal{O}(1)$ |
mapping[key] |
$\mathcal{O}(1)$ |
mapping.get(key) |
$\mathcal{O}(1)$ |
mapping.pop(key) |
$\mathcal{O}(1)$ |
key in mapping |
$\mathcal{O}(1)$ |
for k, v in mapping.items() |
$\mathcal{O}(n)$ |
next(iter(mapping)) |
$\mathcal{O}(1)$ |
next(reversed(mapping)) |
$\mathcal{O}(1)$ |
value in mapping.values() |
$\mathcal{O}(n)$ |
mapping.update(iterable) |
$\mathcal{O}(k)$ |
set
| operation | time complexity |
|---|---|
my_set.add(item) |
$\mathcal{O}(1)$ |
my_set.remove(item) |
$\mathcal{O}(1)$ |
item in my_set |
$\mathcal{O}(1)$ |
for item in my_set |
$\mathcal{O}(n)$ |
set1 & set2 |
$\mathcal{O}(n)$ |
set1 | set2 |
$\mathcal{O}(n)$ |
set1 ^ set2 |
$\mathcal{O}(n)$ |
set1 - set2 |
$\mathcal{O}(n)$ |
counter
| operation | time complexity |
|---|---|
counter[item] |
$\mathcal{O}(1)$ |
counter.pop(item) |
$\mathcal{O}(1)$ |
for k, v in counter.items(): |
$\mathcal{O}(n)$ |
for k, v in counter.most_common(): |
$\mathcal{O}(n\log(n))$ |
for k, v in counter.most_common(k): |
$\mathcal{O}(n \log(k))$ |
counter.update(iterable) |
$\mathcal{O}(k)$ |
counter.subtract(iterable) |
$\mathcal{O}(k)$ |
counter.total() |
$\mathcal{O}(n)$ |
heap / priority queue
| operation | time complexity |
|---|---|
heapq.heapify(sequence) |
$\mathcal{O}(n)$ |
heapq.heappop(sequence) |
$\mathcal{O}(\log(n))$ |
heapq.heappush(sequence, item) |
$\mathcal{O}(\log(n))$ |
sequence[0] |
$\mathcal{O}(1)$ |
sorted list
| operation | time complexity |
|---|---|
sorted_sequence = sorted(sequence) |
$\mathcal{O}(n\log(n))$ |
sorted_sequence.index(item) |
$\mathcal{O}(n)$ |
bisect.bisect(sorted_sequence, item) |
$\mathcal{O}(\log(n))$ |
bisect.insort(sorted_sequence, item) |
$\mathcal{O}(n)$ |
general traversals:
| operation | time complexity |
|---|---|
min(iterable) |
$\mathcal{O}(n)$ |
max(iterable) |
$\mathcal{O}(n)$ |
sorted(iterable) |
$\mathcal{O}(n\log(n))$ |
heapq.nsmallest(k, iterable) |
$\mathcal{O}(n\log(k))$ |
statistics.multimode(iterable) |
$\mathcal{O}(n)$ |
Footnotes
1
information courtesy of https://www.pythonmorsels.com/time-complexities/