What Is Auxiliary Space? Measuring an Algorithm's Extra Memory
Auxiliary space is the memory an algorithm uses beyond its input. A few counters are O(1), a table that grows with the input is O(n), and recursive call-stack frames count too.
Auxiliary space is the extra memory an algorithm needs while it runs, beyond the input it was given. Space complexity is the broader growth description; when a course asks for extra space, it usually wants the auxiliary-space bound.
A few counters and indexes use O(1) auxiliary space because their number does not grow with the input. A hash table with one entry per value uses O(n). A recursive algorithm also uses memory for active call-stack frames, even when it allocates no explicit array.
Choose and state a convention
Some analyses report total space, including the input and required output. Others report auxiliary space and discuss output separately. Both conventions can be useful, but mixing them makes comparisons misleading.
State the convention in the answer. For example:
- sorted squares takes O(n) time, O(n) output space, and O(1) auxiliary space beyond the output;
- merge sort takes O(n log n) time and O(n) auxiliary space for temporary arrays;
- iterative binary search takes O(log n) time and O(1) auxiliary space;
- recursive binary search also keeps O(log n) call-stack space.
The input array already exists before the function runs, so merely reading it does not allocate O(n) auxiliary space.
A constant-space scan
This function retains a count and one current value. Neither amount grows with the array length.
Press Run to execute this example. Use console.log to print a value.
The time is O(n) because every value is inspected. The auxiliary space is O(1) because the loop stores a fixed number of variables. Time and space are separate measurements.
Output space versus working space
Suppose a function returns a reversed copy of an array. The result necessarily contains n values, so output space is O(n). If the function fills that result using only an index and a temporary value, its auxiliary space beyond the required output is O(1).
If the same function first creates another full copy and then creates the result, that temporary copy adds O(n) auxiliary space. Saying “the output already costs O(n)” does not make the extra copy free.
This distinction matters when two correct implementations return the same required result. Their output cost is identical, while their working-memory costs can differ.
Recursion and the call stack
Every active function call keeps a frame containing its parameters, local variables, and return location. A recursive traversal with maximum depth d therefore uses O(d) call-stack space.
A balanced binary tree has O(log n) height, so a depth-first recursive walk uses O(log n) stack space. A one-sided tree has height O(n), so the same code uses O(n) stack space.
Tail-recursive code is not automatically O(1) space in JavaScript. Do not assume tail-call optimisation unless the runtime and execution mode explicitly guarantee it.
Peak space, not total allocation
Space complexity normally measures the maximum memory simultaneously live, not every allocation made over time. Merge sort may allocate arrays in many recursive calls, but arrays from completed branches can become unreachable.
Analyze which allocations coexist at the peak. In the standard merge-sort implementation, temporary array storage is O(n) at peak, plus O(log n) call-stack frames for balanced splitting.
Common examples
| Technique | Typical auxiliary space | Why |
|---|---|---|
| Counter or two pointers | O(1) | Fixed number of variables |
| Hash-based frequency count | O(u) | One entry per distinct value |
| BFS on a graph | O(V) beyond adjacency storage | Queue and visited set |
| Recursive tree traversal | O(h) | One frame per active level |
| Dynamic-programming table | O(n) | One stored answer per state |
| Rolling DP variables | O(1) | Only recent states remain live |
Here u is the number of distinct values, V the number of vertices, and h the tree height. Naming the relevant dimension is more informative than writing O(n) for everything.
In the course
The course asks for time and auxiliary space together. Two Sum spends O(n) extra memory to avoid a quadratic pair scan. Sliding-window sums keep O(1) state. Graph traversal stores an adjacency list, a visited set, and a frontier. Dynamic programming may keep a full bottom-up table or compress it to the few states the recurrence still needs.
Report required output separately when that distinction clarifies the algorithm. Count recursive stack frames even when the code contains no explicit stack.
Common mistakes
Do not count the input as auxiliary space merely because its length is n.
Do not ignore the call stack in a recursive function.
Do not call a second n-element array O(1) space because the function returns another n-element array.
Do not add every allocation ever made. Measure the peak amount of memory that remains live at the same time.