Space complexity
Also known as: Memory complexity, Auxiliary space
Space complexity measures memory as a function of input size. Distinguish total space from auxiliary space (extra beyond the input). An in-place heapsort uses $O(1)$ auxiliary words; merge sort typically needs $\Theta(n)$ auxiliary.
Recursion depth counts: a naive recursive DFS can use $O(V)$ stack frames. Streaming algorithms aim for sublinear extra space.
Trade space for time when tables, caches, or memoization (DP) remove repeated work.