A solution can be correct and still be too slow or too large. Performance asks what it costs to run an algorithm: time, memory, or another resource that matters to its users. The answer depends on both the size of the problem and the operations the program actually performs. section 1.1 section 1.4
Big O notation describes how cost grows as input size increases. Accessing the first array element is O(1); summing n integers is O(n). Growth rate is useful, but it is not a stopwatch reading: for consistently small problems, asymptotic complexity may matter less than the cost of a particular implementation. section 1.1 section 1.4
Figure 1.1 A graph comparing the growth curves for logarithmic, linear, quasilinear, quadratic, and exponential growth. The logarithmic curve is the shallowest, growing slowly, and the exponential curve is the fastest.
The growth curves make the distinction between logarithmic, linear, quadratic, and exponential scaling visible. section 1.1
Ask more than “How fast is it?”
- Which operation? An immutable queue makes Enqueue O(1), but a Dequeue that reverses n pending items can take O(n) time and space. Across a sequence of operations, its amortized dequeue cost is O(1). section 2.4
- Which resource? A naïve immutable deque allocates O(n) nodes per push or pop; its recursive enumeration takes O(n²) time and O(n) stack space. section 3.2
- Which phase? A categorical sampler can trade O(W) construction space and time for O(1) sampling, or use O(n) construction resources with O(n) sampling. section 12.9
- Which case? Binary term unification is typically quick, yet substitution in a constructed worst case allocates O(2ⁿ) objects. section 10.2
A faster machine does not change the growth rate
A GPU implementation of a naïve Game of Life update can run roughly 200 times faster than an array implementation. Both still inspect every simulated cell each tick, so both remain O(n) per tick. Tracking only the active region changes what n counts; memoizing repeated quadtree computations instead trades cache memory for saved work. Neither optimization has a guaranteed payoff without examining the workload. section 4.2.2 section 4.2.3 section 4.4.4
A good comparison therefore combines analysis with concrete costs. A sorted word list’s binary search takes O(m log n) for words of typical length m, but storing the strings and references also consumes bytes. A trie shares prefixes, yet its nodes and dictionaries have overhead. Measure the representation as well as the search. section 5.1.2 section 5.2.4
