Chapter 1: Fundamentals

A data structure is a triple $(S, \text{Ops}, \text{Costs})$ where $S$ is the set of states, $\text{Ops}$ are the supported operations, and $\text{Costs}: \text{Ops} \to \mathbb{R}_{\ge 0}$ is the cost model. Choosing a structure means minimising $\sum_{i} f_i \cdot c(op_i)$ where $f_i$ is how often each operation is performed. For a workload with $N$ lookups and $M$ inserts, a hash set costs $O(N + M)$ while a sorted array costs $O(N \log N + M \cdot N)$ — the right choice can change the total by a polynomial factor.

$f(n) = O(g(n))$ iff there exist constants $c > 0$ and $n_0 \ge 0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$. This definition ignores constants and lower-order terms because for any polynomial $a n^k + b n^{k-1} + \dots$, the dominant term eventually dwarfs the rest: $\lim_{n \to \infty} \frac{a n^k}{a n^k + b n^{k-1}} = 1$. Big O is an upper bound on growth, giving a machine-independent way to compare algorithms.

Space complexity counts the extra memory used as a function of input size $n$, excluding the input itself. For a recursive algorithm with recursion depth $d$ and local variables of size $s$, space is $O(d \cdot s)$ because the call stack holds $d$ frames simultaneously. Example: merge sort uses $O(n)$ auxiliary space for the merge buffer plus $O(\log n)$ for recursion, totalling $O(n)$.