Analysis of Algorithms

All animations

52 animations, in a sensible learning order. Start anywhere: each one opens with Previous and Next buttons and a menu to jump to any other.

Counting steps

How much work does code do? Count every line, add it up into T(n), and find the Big-O.

Growth rates and Big-O

Big-O, Big-Ω and Big-Θ, proved with c and n₀ and drawn on a graph.

Limits and loop invariants

Compare growth with limits, and prove loops correct with invariants.

Sorting

Watch the classic sorts swap, shift and settle, with the code running alongside.

Recursion

How recursive calls run on the call stack, and how to write their recurrences.

Solving recurrences

Four methods: iteration, substitution, recursion trees and the Master Theorem.

Read the notes

Binary search trees

Insert, search, delete, min, max, successor, predecessor and traversals. Build your own tree.