Algorithm Space Complexity and Auxiliary Storage

Time complexity gets most of the attention in interviews, but almost every follow-up eventually turns to memory: “Can you do it without the extra array?”, “What’s the space complexity of your recursion?”, “Is that really constant space?” Answering well means knowing what to count, and spotting the memory that code uses without announcing it.

This note measures real memory use with Python’s built-in tracemalloc module, which reports the peak amount of memory Python allocated while a piece of code ran. All numbers come from Python 3.14 on an M1 MacBook Pro. Exact byte counts depend on the interpreter version; the growth patterns don’t.

Three kinds of memory

When someone asks for an algorithm’s space complexity, they could mean three different things:

• Input: the data you were given. Everyone has to store it, so it’s usually left out.
• Output: memory for the answer. If the problem asks you to return a new array of length n, that O(n) is unavoidable.
• Auxiliary: everything else your algorithm allocates while it works. Hash maps, temporary arrays, the recursion stack.

In interviews “space complexity” almost always means auxiliary space. Whether the output counts varies, which is why problems like Product of Array Except Self spell it out: “O(1) extra space, not counting the output array”. When it isn’t spelled out, state your assumption: “That’s O(n) total, or O(1) auxiliary if we don’t count the result.” It takes five seconds and removes any ambiguity.

The memory you trade for speed

Most time savings in interview problems come from spending memory. Checking a million integers for duplicates with a set is O(n) time and O(n) space. Sorting first and comparing neighbours is O(n log n) time and, in principle, less space. Measuring both on a million distinct integers:

def dup_set(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

def dup_sort_in_place(nums):
    nums.sort()                      # mutates the caller's list
    return any(nums[i] == nums[i - 1] for i in range(1, len(nums)))

dup_set: peak extra memory 48.0 MiB
dup_sort_in_place: peak extra memory 3.8 MiB

The set costs 48 MiB for a million entries: hash tables keep empty slots to stay fast, and growing the table briefly holds the old and new versions at once. The sort is much cheaper, but notice it isn’t zero. Python’s sort (Timsort) merges runs using a temporary buffer of up to n / 2 references, which here is about half a million 8-byte pointers, roughly 3.8 MiB. So “sort in place” is O(n) auxiliary in CPython, not O(1). Heapsort is the classic comparison sort that’s truly O(1) auxiliary, at the cost of being slower in practice. If an interviewer presses on “constant space”, this is a detail worth knowing.

The in-place sort also mutates the caller’s list, which is a different kind of cost. Ask whether you’re allowed to modify the input before relying on it.

Recursion is memory too

Every active function call holds a stack frame: its local variables, arguments and return address. A recursive function that goes d levels deep holds d frames at once, so its auxiliary space is at least O(d), even if it never allocates a single list.

For trees, d is the height. Here’s a depth calculation that also records how many frames were on the stack at the deepest point, run on two trees: a balanced tree of 1,000 nodes, and a “skewed” tree of 900 nodes where every node has only a left child, which is really a linked list in disguise.

def max_depth(node, depth=1):
    global deepest
    if node is None:
        return 0
    deepest = max(deepest, depth)         # how many frames are on the stack right now
    return 1 + max(max_depth(node.left, depth + 1), max_depth(node.right, depth + 1))

balanced: height=10, deepest stack=10 frames
skewed: height=900, deepest stack=900 frames
skewed 5000: RecursionError

Same algorithm, same number of nodes (roughly), and a 90-fold difference in stack usage. That’s why the space complexity of a recursive tree traversal is O(h), which is O(log n) for a balanced tree and O(n) in the worst case. A skewed tree of 5,000 nodes exceeds CPython’s default limit of 1,000 frames and crashes. Maximum Depth of Binary Tree is the place to practise saying this precisely.

Iterative versions don’t escape the cost; they move it. An iterative depth-first search keeps an explicit stack that can grow just as large. What changes is that the explicit stack lives on the heap, which has far more room than the call stack.

Hidden copies

The memory leaks that hurt most in interview code are copies you didn’t mean to make. In Python, slicing creates a new list. Here’s a recursive binary search written the “elegant” way, passing slices, next to the usual index version, both searching a million-element list:

def contains_slicing(arr, target):
    if not arr:
        return False
    mid = len(arr) // 2
    if arr[mid] == target:
        return True
    if arr[mid] < target:
        return contains_slicing(arr[mid + 1:], target)   # copies half the list
    return contains_slicing(arr[:mid], target)

binary search with slicing: peak 7,813 KiB
binary search with indexes: peak 0.0 KiB

The slicing version copies 500,000 references, then 250,000, then 125,000, and all of those copies are alive at once because each recursive call is still waiting for its child. The total is about n references, nearly 8 MB, so the space is O(n). The copying also costs O(n) time, which quietly destroys the O(log n) that binary search exists to provide. The index version allocates nothing worth measuring. String concatenation in a loop, list(...) around something that’s already a list, and sorted() (which returns a new list, unlike .sort()) are other common sources of copies.

Auxiliary space, step by step

When you’re asked for space complexity, work through the code in this order:

1. Data structures you create. Each map, set, list or matrix, and how its size depends on the input.
2. Recursion depth. The deepest the call stack can go, times the memory each frame holds.
3. Copies. Slices, concatenations, conversions, especially inside loops or recursive calls.
4. Output. Note it, and state whether you’re including it.

Then report the largest term. For the solution to Move Zeroes, which shuffles non-zero values forward with two indexes, all four are empty except the input, so it’s O(1) auxiliary. For a memoised Fibonacci, the cache holds n entries and the recursion is n deep, so O(n); the iterative version with two variables is O(1).

Interview practice: the innocent recursive sum

A candidate writes this to sum a list recursively:

def total_slicing(nums):
    if not nums:
        return 0
    return nums[0] + total_slicing(nums[1:])

What are its time and space complexity? How would you fix each?

Answer

Both are O(n²). The recursion goes n levels deep. At each level, nums[1:] copies the remaining list, so the copies have lengths n - 1, n - 2, …, down to 0. Copying costs time proportional to length, which sums to about n² / 2 operations. And because every level is waiting for the level below it to return, all of those copies exist simultaneously at the deepest point, so peak memory is also about n² / 2 references.

Measuring peak memory for three versions confirms it: the slicing version, a recursive version that passes an index instead of a slice, and a plain loop.

def total_index(nums, i=0):
    if i == len(nums):
        return 0
    return nums[i] + total_index(nums, i + 1)

def total_loop(nums):
    s = 0
    for x in nums:
        s += x
    return s

n=1000: slicing    3,953 KiB   index recursion    23 KiB   loop 0.0 KiB
n=2000: slicing   15,722 KiB   index recursion    51 KiB   loop 0.0 KiB
n=4000: slicing   62,699 KiB   index recursion   114 KiB   loop 0.0 KiB

Read the columns as n doubles. The slicing version roughly quadruples each time, the signature of O(n²). The index version roughly doubles: no copies, but still n stack frames, so O(n) space and O(n) time. The loop stays flat at O(1) auxiliary space, with O(n) time. (The recursive versions needed sys.setrecursionlimit(10_000) to run at n = 4,000, which is its own argument for the loop.)

The fixes, in order: pass an index instead of a slice to remove the copies, then replace the recursion with a loop to remove the stack. In real Python code you’d write sum(nums). In an interview, the point of the question is that the candidate spots both hidden costs, the copies and the frames, and explains why the copies are simultaneous rather than one at a time. That’s what makes the space quadratic rather than linear.

Related notes

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Big-O Complexity and Input Growth, the time half of the analysis
• Tree Traversals and Information Flow, where recursion depth matters most
• MIT 6.006 Introduction to Algorithms (Spring 2020)