Space Complexity
The other axis interviewers probe: auxiliary space, the hidden cost of the recursion call stack, and the classic time-vs-space trade-off.
On this page
Time complexity gets all the attention, but interviewers almost always ask the follow-up: "and the space complexity?" Getting it right - especially the hidden cost of recursion - is what separates a polished answer from a shaky one.
Auxiliary space is what counts
Space complexity measures the extra memory an algorithm uses as a function of input size. The key word is extra: we usually count auxiliary space - memory you allocate beyond the input itself - because the input has to exist regardless.
- Reversing an array in place with two pointers → O(1) auxiliary space.
- Copying it into a new array → O(n).
- Building a hash set of all n elements → O(n).
// O(1) extra space: swap in place
int i = 0, j = a.length - 1;
while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
// O(n) extra space: a new structure sized to the input
Set<Integer> seen = new HashSet<>(); // grows to n entries
for (int x : a) seen.add(x);The recursion call stack is not free
Here's the trap that catches people: every recursive call uses stack memory for its frame, and that stack depth counts toward space complexity even when you allocate nothing else.
// O(n) SPACE, not O(1): the call stack goes n frames deep
int sum(int[] a, int i) {
if (i == a.length) return 0;
return a[i] + sum(a, i + 1); // one stack frame per element
}That recursion uses no arrays, yet it's O(n) space because n frames pile up before any return. A binary search or a balanced-tree traversal recurses only O(log n) deep, so it's O(log n) space. An iterative version of the same sum, with a plain loop, is O(1) space - which is often why an interviewer asks you to convert recursion to iteration.
Deep recursion can overflow the stack
The call stack is a fixed, fairly small region of memory. Recursion that goes O(n) deep on a large input can throw StackOverflowError - a real production bug, not just a complexity nicety. Balanced recursion (O(log n) deep) is safe; linear recursion over big inputs often needs to become a loop or use an explicit stack.
Imagine opening a package, and inside is another package you set aside to open next, and inside that another - you keep stacking the half-opened boxes on your desk. Even though you're not keeping anything, the pile of paused boxes takes up desk space until you finish and clear them from the top down. Recursive calls are those paused boxes: each waits on the one inside it, and the whole pile occupies memory until the innermost returns and they collapse back.
You need to print the numbers 1 to n. Compare a recursive print(n) that calls print(n-1) first,
versus a simple for loop. Both are O(n) time - what's the space complexity of each, and why would
an interviewer prefer the loop for large n?
What is the space complexity of a recursive function that calls itself once per element, n levels deep, allocating nothing else?
Key takeaways
- Space complexity counts auxiliary memory - what you allocate beyond the input.
- In-place algorithms are O(1) space; building a new structure sized to the input is O(n).
- The recursion call stack costs memory: depth d recursion is O(d) space even if it allocates nothing.
- Linear recursion over large inputs is O(n) space and can overflow the stack - convert to a loop or explicit stack.
- Interviewers frequently ask for the time-vs-space trade-off, so state both for every solution.