Space Complexity

Counting memory, not steps

Time complexity asks how many operations? Space complexity asks how much extra memory?

The word extra is doing a lot of work there. You do not count the input itself — it already exists, and you had no say in it. You count what your algorithm adds on top.

def find_max(nums):
    best = nums[0]        # one variable
    for n in nums:
        if n > best:
            best = n
    return best

The input might be a million numbers, but this function adds one variable. That is $O(1)$ space — constant, regardless of input size.

def double_all(nums):
    return [n * 2 for n in nums]    # a new list of size n

This builds a second list as large as the input, so it is $O(n)$ space.

The rule that catches people out

Recursion costs memory even when you allocate nothing.

Every pending function call occupies a stack frame holding its parameters, local variables, and return address. The frames pile up until the base case returns.

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

No list is created. No dictionary. And yet this is $O(n)$ space, because at the deepest point there are $n$ frames stacked up:

sum_list(nums, 0)   ← still waiting
  sum_list(nums, 1)   ← still waiting
    sum_list(nums, 2)   ← still waiting
      ...
        sum_list(nums, n)   ← finally returns

The iterative version does the same work in $O(1)$ space:

def sum_list(nums):
    total = 0
    for n in nums:
        total += n
    return total

Recursion depth is space complexity. Say this out loud in an interview and it lands well, because most candidates forget it.

Common classes

Worked examples

Binary search

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Three variables → $O(1)$ space.

But write it recursively and each call adds a frame. The depth is $\log n$, so it becomes $O(\log n)$ space. Same algorithm, same time complexity, different memory — purely because of how it is written.

Merge sort vs quicksort

Both are $O(n \log n)$ time, but their memory differs:

• Merge sort builds temporary arrays when merging → $O(n)$ space
• Quicksort partitions in place, only the recursion stack costs → $O(\log n)$ space on average

That difference is often the deciding factor. It is also why quicksort is the usual default despite its worse worst case.

Two pointers vs hash map

For "find two numbers that sum to a target":

# Hash map: O(n) time, O(n) space
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i

# Two pointers on sorted input: O(n) time, O(1) space
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1

Same time, but the second uses no extra memory. The catch is that it needs sorted input. This is the space-time tradeoff in miniature: the hash map buys the ability to work on unsorted data by spending $O(n)$ memory.

In-place algorithms

An in-place algorithm modifies the input directly using $O(1)$ extra space.

def reverse(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

No new list. Just swaps.

The trade-off is that you destroy the original. If the caller still needs it, in-place is the wrong choice — and an interviewer may specifically ask whether mutating the input is acceptable.

The output does not count

There is one useful convention: space needed for the output is usually excluded.

def all_subsets(nums):
    result = []
    # ... generates 2^n subsets
    return result

Strictly this is $O(2^n \times n)$ memory. But since the problem asks for every subset, that memory is unavoidable — so we usually describe it as $O(n)$ auxiliary space (the recursion depth and the working list).

If asked, be explicit: "$O(n)$ auxiliary space, plus $O(2^n \times n)$ for the output itself." That precision is exactly what distinguishes a strong answer.

Try it

No data structures at all — but the recursion goes $n$ levels deep, so it is $O(n)$ space and $O(n)$ time. The iterative version would be $O(1)$ space.

When memory actually matters

• Very large inputs — a million items times $O(n)$ extra can exhaust RAM
• Embedded systems where memory is genuinely scarce
• Streaming data too large to hold at all, forcing $O(1)$ or $O(k)$ solutions
• Interviews where the follow-up is always "can you do it in $O(1)$ space?"

That last one is the practical reason to care. Solving it, then improving the memory, is exactly the progression interviewers want to see.

Common mistakes

1. Forgetting recursion depth. The most common error by far.
2. Counting the input as part of space complexity.
3. Missing hidden copies — nums[1:] in Python copies the slice.
4. Assuming in-place is always better. It destroys the input.
5. Ignoring the cost of the call stack when comparing recursive and iterative solutions.
6. Not distinguishing auxiliary space from output space on generation problems.

Summary

Space complexity counts the extra memory you add, not the input. Recursion depth counts even when you allocate nothing, which is what most people miss. Learn the classic tradeoffs — hash map versus two pointers, merge sort versus quicksort — and be ready for "now do it in $O(1)$ space".