Overview
Measuring an algorithm by timing it tells you about your laptop, your compiler, your input, and the
Big-O Notation
Big-O describes an upper bound on growth. Saying an algorithm is $O(n^2)$ claims that beyond some
Common Complexities
In practice you meet perhaps eight growth classes. Recognising which one a piece of code falls into —
Amortized Analysis
Some structures cannot be made cheap on every single call, but can be made cheap *on average over any
Recurrences & the Master Theorem
A recursive algorithm's cost is itself defined recursively — mergesort's cost on n elements is twice its
Space Complexity
Time complexity answers "how does the work grow?"; space complexity asks the same question about
P, NP & Intractability
Most complexity analysis on this site asks how fast a known algorithm runs. This page asks a
Cheat Sheet
This page is a reference, not a tutorial — each numbered page in this section explains the reasoning