auxiliary space

The memory an algorithm allocates beyond the input itself, such as a temporary copy or a helper array.

In more detail

Space complexity usually means auxiliary space, since the input has to exist anyway. Merge sort needs O(n) auxiliary space for merging, while heap sort needs only O(1). Counting sort's count array is auxiliary space proportional to the key range.

Related terms

Taught in

References