Algorithms — Engineering
Notes for Working Code
A working reference for the algorithms that show up in real systems — complexity first, then sorting, searching, graphs, dynamic programming and the design paradigms underneath them. Every chapter pairs the idea with a clean implementation and the cost you actually pay.
Big-O describes an upper bound on growth: an algorithm is O(f(n)) if, past some input size, its running time never exceeds a constant multiple of f(n). We drop constants and lower-order terms because they stop mattering as n grows.
| Notation | Bound | Reads as |
|---|---|---|
| O(f) | upper | "grows no faster than f" |
| Ω(f) | lower | "grows at least as fast as f" |
| Θ(f) | tight | "grows exactly like f" |
From cheapest to most expensive, the classes you meet daily:
# cheapest → most expensive O(1) # constant — hash lookup O(log n) # logarithmic — binary search O(n) # linear — scan an array O(n log n) # linearithmic — good sorts O(n^2) # quadratic — naive nested loops O(2^n) # exponential — naive subsets O(n!) # factorial — naive permutations
O(n^2) is fine to ~10,000 elements, O(n log n) to ~10 million, O(n) to ~100 million. If n is large and you wrote a nested loop, that's usually the thing to fix first.Space complexity counts extra memory beyond the input. Amortised cost averages an expensive-but-rare operation over the cheap common ones — a dynamic array's push is O(1) amortised even though the occasional resize is O(n).
Every correct recursion has a base case that stops it and a recursive case that moves strictly toward the base. Miss either and you get a stack overflow.
def factorial(n): if n <= 1: # base case return 1 return n * factorial(n - 1) # shrinks toward base
For divide-and-conquer recurrences of the form T(n) = a·T(n/b) + O(n^d):
if d > log_b(a): T(n) = O(n^d) if d = log_b(a): T(n) = O(n^d log n) if d < log_b(a): T(n) = O(n^(log_b a)) # merge sort: a=2, b=2, d=1 → 1 = log2(2) → O(n log n)
Any recursion can be rewritten with an explicit stack. Recursion is clearer for tree/graph shapes; iteration avoids call-stack limits. Tail calls aren't optimised in most mainstream runtimes — assume each call costs a frame.
def selection_sort(a): for i in range(len(a)): m = i for j in range(i+1, len(a)): if a[j] < a[m]: m = j a[i], a[m] = a[m], a[i] # swap min into place def insertion_sort(a): for i in range(1, len(a)): key, j = a[i], i - 1 while j >= 0 and a[j] > key: a[j+1] = a[j]; j -= 1 a[j+1] = key
O(n) on already-mostly-sorted data and has tiny constants, which is why production sorts (Timsort, introsort) fall back to it for small or nearly-sorted subarrays.def merge_sort(a): if len(a) <= 1: return a mid = len(a) // 2 L = merge_sort(a[:mid]) R = merge_sort(a[mid:]) return merge(L, R) def merge(L, R): out, i, j = [], 0, 0 while i < len(L) and j < len(R): if L[i] <= R[j]: out.append(L[i]); i += 1 else: out.append(R[j]); j += 1 return out + L[i:] + R[j:]
def quicksort(a, lo, hi): if lo >= hi: return p = partition(a, lo, hi) quicksort(a, lo, p-1) quicksort(a, p+1, hi) def partition(a, lo, hi): pivot, i = a[hi], lo for j in range(lo, hi): if a[j] < pivot: a[i], a[j] = a[j], a[i]; i += 1 a[i], a[hi] = a[hi], a[i] return i
def heapify(a, n, i): big = i; l, r = 2*i+1, 2*i+2 if l < n and a[l] > a[big]: big = l if r < n and a[r] > a[big]: big = r if big != i: a[i], a[big] = a[big], a[i] heapify(a, n, big) def heapsort(a): n = len(a) for i in range(n//2-1, -1, -1): heapify(a, n, i) for i in range(n-1, 0, -1): a[0], a[i] = a[i], a[0] heapify(a, i, 0)
Building the heap is O(n) (not O(n log n) — a tighter analysis); the n extractions are O(n log n) total. Use heapsort when you need a worst-case guarantee with no extra memory.
When keys are small integers in a known range [0, k], tally occurrences and rebuild. O(n + k), stable.
def counting_sort(a, k): count = [0] * (k+1) for x in a: count[x] += 1 out = [] for v in range(k+1): out += [v] * count[v] return out
Sort by least-significant digit first, using a stable counting sort per digit. O(d·(n + b)) for d digits in base b.
def binary_search(a, target): lo, hi = 0, len(a) - 1 while lo <= hi: mid = (lo + hi) // 2 if a[mid] == target: return mid if a[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
The real power: when a predicate is monotonic (false…false, true…true), binary-search the boundary. "Smallest capacity that ships in D days", "minimum max-page split" — all the same template. The array doesn't have to exist; the answer space just has to be sorted by feasibility.
(lo+hi)/2 (use lo + (hi-lo)//2 in fixed-width languages), and infinite loops from the wrong lo/hi update when searching for a boundary rather than an exact value.On a sorted array, converge from both ends. Classic: does a pair sum to a target?
def has_pair(a, target): # a is sorted i, j = 0, len(a) - 1 while i < j: s = a[i] + a[j] if s == target: return True if s < target: i += 1 else: j -= 1 return False
Grow the window's right edge; when a constraint breaks, shrink from the left. Longest substring without repeats, minimum window covering a set, max sum of size-k — all this shape. Each element enters and leaves the window once → O(n).
Three steps: divide the problem into subproblems of the same kind, conquer them recursively, combine their answers. The combine step's cost drives the recurrence (see the Master Theorem in Ch. 02).
def max_sub(a, lo, hi): if lo == hi: return a[lo] mid = (lo + hi) // 2 left = max_sub(a, lo, mid) right = max_sub(a, mid+1, hi) cross = cross_sum(a, lo, mid, hi) return max(left, right, cross)
O(n log n) here; Kadane's DP (Ch. 12) does the same in O(n). Divide-and-conquer isn't always optimal — but it's often the first correct thing you can reason about.
Greedy is valid only when the problem has the greedy-choice property (a global optimum contains a locally optimal first step) and optimal substructure. Activity selection, Huffman coding, Kruskal's and Prim's MSTs, and Dijkstra are correct greedies. The 0/1 knapsack is the classic where greedy fails and you need DP.
# Interval scheduling: pick the most activities def max_activities(intervals): intervals.sort(key=lambda x: x[1]) # by end time count, end = 0, -float('inf') for s, e in intervals: if s >= end: count += 1; end = e return count
# Top-down: recursion + cache from functools import lru_cache @lru_cache(None) def fib(n): return n if n < 2 else fib(n-1) + fib(n-2) # Bottom-up: fill a table, O(1) space here def fib_bu(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a
def knapsack(wt, val, W): dp = [0] * (W+1) for i in range(len(wt)): for c in range(W, wt[i]-1, -1): # reverse! dp[c] = max(dp[c], dp[c-wt[i]] + val[i]) return dp[W]
def permute(nums): res, n = [], len(nums) def bt(path, used): if len(path) == n: res.append(path[:]); return for i in range(n): if used[i]: continue used[i] = True; path.append(nums[i]) bt(path, used) path.pop(); used[i] = False # undo bt([], [False]*n) return res
The whole technique is "choose → recurse → un-choose". Add a pruning test before recursing (constraint propagation, bounds) and exponential search spaces become tractable: N-Queens, Sudoku, subset-sum.
Two keys hashing to the same bucket is a collision. Two resolution families: chaining (each bucket holds a list) and open addressing (probe to the next free slot). Keep the load factor (n/buckets) under ~0.75 and resize when it exceeds — amortised O(1) holds, worst case degrades to O(n) on adversarial keys.
Most "is this a duplicate / have I seen this / count occurrences / group by" problems collapse to a hash set or map and one linear pass — turning the obvious O(n^2) into O(n).
import heapq pq = [] heapq.heappush(pq, (priority, item)) priority, item = heapq.heappop(pq) # min by default # Top-k largest in O(n log k): def top_k(a, k): h = a[:k]; heapq.heapify(h) for x in a[k:]: if x > h[0]: heapq.heapreplace(h, x) return h
Parent of index i is (i-1)//2; children are 2i+1 and 2i+2. That index arithmetic is why a heap needs no pointers — it lives in a flat array.
For every node, all keys in the left subtree are smaller and all in the right are larger. Search/insert/delete are O(h) where h is height. A balanced tree has h = O(log n); insert sorted data into a naive BST and h = O(n) — it degenerates into a linked list.
def inorder(node, out): if not node: return inorder(node.left, out) out.append(node.val) inorder(node.right, out)
parent = list(range(n)); rank = [0]*n def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path compression x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra == rb: return if rank[ra] < rank[rb]: ra, rb = rb, ra parent[rb] = ra if rank[ra] == rank[rb]: rank[ra] += 1
With both optimisations, m operations run in O(m·α(n)) where α is the inverse Ackermann function — effectively constant. Powers Kruskal's MST, connected components, and cycle detection in undirected graphs.
| Aspect | Adjacency list | Adjacency matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Edge exists? | O(degree) | O(1) |
| Iterate neighbours | O(degree) | O(V) |
| Best for | sparse graphs | dense / fast edge queries |
Most real graphs are sparse (E ≪ V²), so adjacency list is the default. Reach for a matrix only when the graph is dense or you need constant-time edge existence checks (e.g. Floyd-Warshall).
from collections import deque def bfs(g, start): seen = {start}; q = deque([start]) while q: u = q.popleft() for v in g[u]: if v not in seen: seen.add(v); q.append(v) def dfs(g, u, seen): seen.add(u) for v in g[u]: if v not in seen: dfs(g, v, seen)
Both are O(V + E). BFS explores level by level — its tree gives shortest paths in unweighted graphs. DFS goes deep first — it reveals structure: cycles, bridges, articulation points, topological order, strongly connected components.
import heapq def dijkstra(g, src): dist = {src: 0}; pq = [(0, src)] while pq: d, u = heapq.heappop(pq) if d > dist.get(u, float('inf')): continue for v, w in g[u]: nd = d + w if nd < dist.get(v, float('inf')): dist[v] = nd; heapq.heappush(pq, (nd, v)) return dist
O((V + E) log V) with a binary heap.
| Algorithm | Use when | Cost |
|---|---|---|
| BFS | unweighted, single source | O(V+E) |
| Dijkstra | non-negative weights, single source | O((V+E) log V) |
| Bellman-Ford | negative weights / detect negative cycle | O(V·E) |
| Floyd-Warshall | all pairs, small dense graph | O(V³) |
def kruskal(n, edges): # edges: (w, u, v) edges.sort() mst, total = [], 0 for w, u, v in edges: if find(u) != find(v): union(u, v) mst.append((u, v)); total += w return total, mst
Kruskal is O(E log E) — sort edges, add the cheapest that doesn't form a cycle (union-find detects the cycle). Prim grows one tree from a seed using a priority queue, O((V+E) log V); it wins on dense graphs.
from collections import deque def toposort(g, n): indeg = [0]*n for u in range(n): for v in g[u]: indeg[v] += 1 q = deque([i for i in range(n) if indeg[i] == 0]) order = [] while q: u = q.popleft(); order.append(u) for v in g[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) return order if len(order) == n else None # None ⇒ cycle
If the output is shorter than the vertex count, the graph had a cycle and no valid ordering exists — a free cycle detector.
KMP precomputes a failure table — for each pattern prefix, the length of the longest proper prefix that's also a suffix. On a mismatch it jumps the pattern forward using that table instead of restarting. O(n + m), no backtracking over the text.
def rabin_karp(text, pat): n, m = len(text), len(pat) if m > n: return -1 B, M = 256, 1_000_000_007 hp = ht = 0; h = 1 for _ in range(m-1): h = (h*B) % M for i in range(m): hp = (hp*B + ord(pat[i])) % M ht = (ht*B + ord(text[i])) % M for i in range(n-m+1): if hp == ht and text[i:i+m] == pat: return i if i < n-m: ht = ((ht - ord(text[i])*h)*B + ord(text[i+m])) % M return -1
The rolling hash makes each window O(1) to update → O(n + m) average. Rabin-Karp shines for multi-pattern search (hash all patterns once).
x & (x - 1) # clears the lowest set bit x & -x # isolates the lowest set bit x & (x - 1) == 0 # is x a power of two? (x > 0) x ^ y # XOR — find the single non-paired value (x >> i) & 1 # read bit i x | (1 << i) # set bit i
def gcd(a, b): while b: a, b = b, a % b return a def sieve(n): # primes up to n, O(n log log n) is_p = [True]*(n+1); is_p[0:2] = [False, False] for i in range(2, int(n**.5)+1): if is_p[i]: for j in range(i*i, n+1, i): is_p[j] = False return [i for i, p in enumerate(is_p) if p] pow(base, exp, mod) # fast modular exponentiation, O(log exp)
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Insertion | O(n) | O(n²) | O(n²) | O(1) | yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | no |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | no |
| Counting | O(n+k) | O(n+k) | O(n+k) | O(k) | yes |
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Hash table | — | O(1) | O(1) | O(1) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary heap | — | O(n) | O(log n) | O(log n) |
| Algorithm | Complexity | Note |
|---|---|---|
| BFS / DFS | O(V + E) | traversal, connectivity |
| Dijkstra (heap) | O((V+E) log V) | non-negative weights |
| Bellman-Ford | O(V·E) | handles negative edges |
| Floyd-Warshall | O(V³) | all pairs |
| Kruskal / Prim | O(E log E) | minimum spanning tree |
| Topological sort | O(V + E) | DAG only |