Algorithms cheat sheet

A scannable Algorithms reference: 7 short snippets across 5 topics, each linking back to the lesson it came from.

At a glance

Quick snippets

Complexity and Big-O in practice

Where Big-O stops predicting

import bisect

# Both are O(n log n) sorts, but the built-in is C and wins by a wide margin
items = [random.random() for _ in range(1_000_000)]
sorted(items)                      # built-in Timsort
# a hand-written merge sort in Python would be 50x slower on the same input

# Searching a sorted list: O(log n) probes, but each probe is a Python call
idx = bisect.bisect_left(sorted_items, target)

# A set lookup is O(1) *in the hash*, but a bad hash turns it into O(n)
# and cache misses on a large dict can make a linear scan of a small array win

Reading cost off the code

for i in range(n):        # n
    for j in range(n):    # x n      -> O(n^2)
        work()

for i in range(n):
    for j in range(i, n): # n + (n-1) + ... + 1 = n(n+1)/2, still O(n^2)
        work()

i = 1
while i < n:              # i doubles, so log2(n) steps -> O(log n)
    i *= 2

… 10 more lines in the full lesson.

Growth rates you can feel

import time
import random

def timeit(fn, data, repeats=3):
    best = float('inf')
    for _ in range(repeats):
        start = time.perf_counter()
        fn(data)
        best = min(best, time.perf_counter() - start)
    return best

data = [random.random() for _ in range(1000)]

… 7 more lines in the full lesson.

Full lesson: Complexity and Big-O in practice →

Sorting and searching

Beyond sorted lists

import heapq

# Top-k of a stream without sorting a million items: O(n log k)
def top_k(stream, k):
    heap = []
    for item in stream:
        if len(heap) < k:
            heapq.heappush(heap, item)
        elif item > heap[0]:
            heapq.heapreplace(heap, item)   # drop the smallest of the best so far
    return sorted(heap, reverse=True)

… 11 more lines in the full lesson.

Full lesson: Sorting and searching →

Graph algorithms: BFS, DFS and shortest paths

Representing a graph

from collections import deque

# Adjacency list: the default. O(V + E) space, fast to iterate neighbours
unweighted = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['d', 'e'],
    'd': ['e'],
    'e': [],
}

# Weighted: each neighbour carries the cost of the edge

… 14 more lines in the full lesson.

Full lesson: Graph algorithms: BFS, DFS and shortest paths →

Recursion, backtracking and divide and conquer

Recursion as a contract

from typing import Sequence

# the base case handles the smallest input; the step makes progress
def total(xs: Sequence[int]) -> int:
    if not xs:                       # base: the empty sequence sums to 0
        return 0
    return xs[0] + total(xs[1:])     # step: strictly smaller input

# the same idea without slicing, which copies the whole rest of the list
def total_index(xs: Sequence[int], i: int = 0) -> int:
    if i == len(xs):
        return 0

… 15 more lines in the full lesson.

Full lesson: Recursion, backtracking and divide and conquer →

Frequency maps, sets and hashing techniques

Hazards and guarantees

# 1. Mutable and unhashable keys
#    key = [1, 2]        -> TypeError: unhashable type 'list'
key = (1, 2)             # a tuple is hashable if its elements are
# For a dict inside a key, freeze it: tuple(sorted(d.items()))

# 2. A custom __hash__ must agree with __eq__
class Point:
    __slots__ = ("x", "y")
    def __init__(self, x: int, y: int) -> None:
        self.x, self.y = x, y
    def __eq__(self, other: object) -> bool:
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

… 15 more lines in the full lesson.

Full lesson: Frequency maps, sets and hashing techniques →

FAQ

Related cheat sheets

Data Structures Computer Networks Operating Systems Character Encodings Hashing & Checksums Data Formats

Last refreshed 2026-09-27.