Count extra memory

Space complexity usually describes auxiliary memory: what the algorithm allocates beyond its input and output. A few counters use O(1) extra space; a second array that grows with n uses O(n).

The call stack counts too. A recursive walk with depth n can use O(n) stack space even when each call creates only a few local variables.