Time/Space Complexity

Definition 0.3. An algorithm $\alpha$ that terminates in time $t(n)$ on
all inputs of size $n$ has running time $T(\alpha) := t$.

If $S \subseteq \mathbb{N} \to \mathbb{N}$ is a set of functions, we say
$\alpha$ has time complexity in $S$ (write $T(\alpha) \in S$ or
$T(\alpha) = S$) iff $t \in S$. Similarly for space complexity: $s(n)$
is the memory used on inputs of size $n$.

Worst-case vs. average-case complexity. Most textbooks (and this course)
focus on worst-case: $t(n) = \max$ over all inputs of size $n$. Average
case replaces the max with the expected value over some distribution.

Size measure matters. "Size" of the input is a choice. For a number, $n$ is
the number itself. For a list of length $n$, the size is $n$. For a graph with
$V$ vertices and $E$ edges, the size is usually $V + E$. There is no canonical
choice — the analysis must say which.

Examples:
- Array lookup: $T(n) = 1$ — constant. Lookup doesn't depend on array size.
- Linear search: $T(n) = n$ — linear. Worst case: target not present.
- Matrix multiply (naive): $T(n) = n^3$ — cubic.
- Subsets of an $n$-set: $T(n) = 2^n$ — exponential.

Time vs. space. You can often trade one for the other. Hash tables use
more memory but enable $O(1)$ lookup. Quicksort uses $O(\log n)$ stack space
but $O(n^2)$ worst-case time.