When I was newer to the field, code review feedback was always about time complexity. Big-O of the loop, Big-O of the lookup, can you make this O(n) instead of O(n^2). I do not remember a single review where someone said "this looks good but the space cost is going to wreck us at 100k items". Then I shipped a service that processed click events in batches, ran the math on time complexity, signed off, and watched it OOM in production within an hour. The function was a clean O(n) in time. It was also O(n) in space, because I was building a per-event accumulator dict, and n was a million events per batch.

Time and space complexity are two halves of the same conversation, but the industry talks about one of them roughly ten times more than the other. I want to argue that space is the half that takes you down in production, because time bottlenecks announce themselves with slow responses while space bottlenecks announce themselves with crashes.

Auxiliary space is the number that matters

The first thing I clarify on every code review is the difference between input space and auxiliary (extra) space. Input space is whatever the caller already allocated to give you the data. Auxiliary space is the new memory your function allocates to do its work. When people say "this is O(1) space" about an in-place reverse, they mean auxiliary; they are obviously not pretending the input array does not exist.

Most space discussions confuse the two. A function that returns a new array of size n is not O(1) space, even though it might allocate just one new structure. It is O(n) because the size of that one structure scales with input. A function that uses three integer counters regardless of input size is O(1), period.

The audit I run on any function: ignore the input, ignore the return value, look only at what gets allocated inside the function and held until return. If that scales with n, the auxiliary space is at least O(n).

The recursion-stack trap that everyone hits once

Here is the first space bug I shipped, in spirit if not in code.

def sum_list(arr, i=0):
    if i == len(arr):
        return 0
    return arr[i] + sum_list(arr, i + 1)

Time: O(n), one addition per element. Space: also O(n), because each recursive call sits on the call stack until the base case returns and the values bubble up. On a million-element list, that is a million stack frames, and Python's default recursion limit is around 1000. The function does not run out of memory; it raises RecursionError long before that. Same n, same answer, totally different failure mode than the time analysis predicts.

The iterative version closes the gap.

def sum_list(arr):
    total = 0
    for x in arr:
        total += x
    return total

Same O(n) time, but O(1) auxiliary space. One scalar accumulator, regardless of input size.

This is also why I default to iterative implementations for anything that walks a list, even if the recursive version reads more elegantly. JavaScript and Python both lack reliable tail-call optimisation. The recursive shape that looks innocent in the source code is a stack hazard at scale.

The growth table I keep next to time complexity

Same shape as the time-complexity cheat sheet, but for memory. The numbers below are bytes-of-overhead, not bytes-of-data, and they assume a typical hash-set or hash-map entry costing roughly 50 bytes in a JS or Python runtime.

The middle row is the one that bites in product code. O(n) auxiliary space looks acceptable on the diagram and crashes the server when n is the size of an actual production batch. 50 MB per request, multiply by even five concurrent requests on a 256 MB container, and you are out of memory.

The trade I make all the time

A lot of optimisation is converting time into space and back. The classic example is memoisation: cache the result of an expensive function and time goes down, space goes up. The reverse is also common; if memory is tight, recompute instead of caching.

The instinct I have built up over the years: when I see O(n^2) time and the input is going to be large, I look hard for an O(n)-time-and-O(n)-space rewrite using a hash set, because RAM is much cheaper than CPU and the latency win is usually worth the memory cost. When I see O(n) space on a function that runs in a hot path on a small container, I look for an in-place rewrite even at the cost of slightly more time, because crashing matters more than being a few percent slower.

Two examples of that trade in practice.

// O(n) time, O(n) space: hash set lookup
function hasDuplicates(arr) {
    const seen = new Set();
    for (const x of arr) {
        if (seen.has(x)) return true;
        seen.add(x);
    }
    return false;
}

// O(n log n) time, O(1) auxiliary space: sort and scan
function hasDuplicatesInPlace(arr) {
    arr.sort();
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] === arr[i - 1]) return true;
    }
    return false;
}

The second version mutates the input, which has its own cost (caller might be surprised), but it is genuinely O(1) auxiliary. On a memory-constrained service the second is sometimes the right call, even though the first is the textbook answer.

The two questions I now ask in every code review

After the OOM that started this article, I added two questions to my review template. They do not catch every problem, but they catch the obvious ones.

What allocates inside this function, and does that scale with input? If the answer is "a temporary array the same size as the input", I do not stop the PR, but I want a sentence in the description acknowledging the memory cost and how big n is going to be in production. If the answer is "nothing, it is in-place", great.

What is the recursion depth? If a function recurses, I sketch the call tree mentally and ask whether the depth grows with the input. If yes, and the language does not eliminate tail calls (it does not, for JS or Python), the function is a stack-overflow hazard waiting for the wrong input. Convert to iteration or use an explicit stack.

Space is a budget, not an afterthought

The mental model I land on with juniors is that every function has two budgets, time and space, and you are spending both at once. A 500ms response that uses 5 MB is a different beast from a 500ms response that uses 500 MB, even though the user perceives them identically. The first scales horizontally; the second falls over in a tight container.

Big-O of time is necessary, but if you stop there you are accountable for half the answer. Track auxiliary space alongside it, especially in any function that builds a result-sized data structure or recurses over input. The bugs that hide in the space half are quieter, but when they show up they take the process with them, and that is not a performance discussion. That is an outage.