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
- space complexity — How the extra memory an algorithm needs grows with the input size, written in the same Big O notation as time.
- in-place algorithm — An algorithm that rearranges its input within the input's own memory, using only a constant amount of extra space.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers