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/ ↩︎
notes
unit vs. functional
unit tests are more modular and work within specific packages. they assume everything else is working and only test a small functionality. they are a programmer’s friend.
functional tests treat the entire system as a black-box; i.e. if the program manipulates data, the functional tests go check to see if the data has been manipulated correctly.
functional tests are more involved, and trickier to design. you may need to use profiling tools to find them, and the skill of creating them is often best left to a separate team that enjoys finding bugs.