How to measure whether code will scale, and the classic algorithms for sorting and finding the shortest path. Press play on any sketch to watch it happen.
1 Big-O: how code scales
Big-O describes how the work grows as the input grows. It ignores small details and shows the shape of the growth, which matters far more than your computer's speed once the data gets big.
O(1): the same work whatever the size. A hash table lookup, on average.
O(log n): halves the problem each step. Binary search.
O(n): looks at everything once.
O(n log n): good general-purpose sorting.
O(n²): a loop inside a loop. Fine for small n, painful for large n.
Comparison
1/5 Find one name in a million sorted names.
Growth
n = 1,000
n = 1,000,000
O(log n)
10
20
O(n)
1,000
1,000,000
O(n log n)
10,000
20,000,000
O(n²)
1,000,000
1,000,000,000,000
Rule of thumb: A better algorithm beats faster hardware every time, once the data is large enough.
2 Sorting with merge sort
Merge sort is a classic divide and conquer algorithm. Split the list in half until the pieces are trivially sorted, then merge them back in order. It runs in O(n log n) every time.
Divide: cut the problem in half.
Conquer: solve each half the same way.
Combine: merge two sorted lists by repeatedly taking the smaller front item.
Compared with quicksort: quicksort is often faster in practice, but its worst case is O(n²).
Divide and conquer tree
1/5 Start with an unsorted list and split it in half.
Rule of thumb: Look for divide and conquer whenever a problem can be split into smaller copies of itself.
3 Shortest paths with Dijkstra
Dijkstra's algorithm finds the cheapest route through a graph. It always expands the closest unvisited node next, so once a node is settled, its distance is final. Maps and network routing use the same idea.
Graph: nodes joined by weighted edges.
Greedy step: always visit the closest node you have not finished yet.
Relaxation: if a new route is shorter, update the distance.
Limit: it fails with negative weights. Use Bellman-Ford for those.
Graph diagram
1/5 From A, the neighbours cost B = 4 and C = 1.
Rule of thumb: Use a priority queue to pick the next node, which gives O((V + E) log V).
