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) {{< mnote “slow because popping at start requires shifting all indices down” >}} | \(\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)\) |
information courtesy of https://www.pythonmorsels.com/time-complexities/ ↩︎