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.
Analyse your own functionPaste any C function and get its T(n) and Big-O.
Sum of an arrayOne loop, counted line by line.
Linear search, worst caseWhat happens when the key isn't there.
Two loops in a rowLoops in sequence add up.
Nested loopsA loop inside a loop multiplies.
Inner loop up to iWhere n(n+1)/2 comes from.
Halving loopWhy halving gives log n.
Constant timeCode that doesn't grow with n.
Steps as cubes: one loopOne cube per step: a single row.
Steps as cubes: nested loopsThe cubes fill an n × n square.
Steps as cubes: bubble sortA triangle of comparisons.
Steps as cubes: binary searchHalf the range disappears each step.
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.
Iteration: T(n − 1) + cUnroll it into O(n).
Iteration: T(n/2) + cUnroll it into O(log n).
Iteration: 2T(n/2) + nUnroll it into O(n log n).
Substitution: O(n log n)Guess, assume, substitute, check.
Substitution: O(n²)Induction on n − 1.
Substitution: O(log n)The base-case trap.
Recursion tree: 2T(n/2) + nEvery level costs the same.
Recursion tree: 3T(n/4) + n²The root dominates.
Recursion tree: 4T(n/2) + nThe leaves dominate.
Master Theorem: case 22T(n/2) + n is Θ(n log n).
Master Theorem: binary searchT(n/2) + 1 is Θ(log n).
Master Theorem: case 19T(n/3) + n is Θ(n²).
Master Theorem: case 32T(n/2) + n² is Θ(n²).
Binary search trees
Insert, search, delete, min, max, successor, predecessor and traversals. Build your own tree.
Build a BSTInsert keys one by one.
SearchFound and not found.
Minimum and maximumLeftmost and rightmost.
SuccessorThe next bigger key.
PredecessorThe next smaller key.
Delete a leafNo children: just remove it.
Delete a node with one childThe child moves up.
Delete a node with two childrenCopy the successor, then delete it.
Inorder traversalGives the keys in sorted order.
Preorder traversalNode before its children.
Postorder traversalChildren before the node.