Space Complexity

Space complexity describes how much memory an algorithm uses as the input size grows. It usually focuses on extra memory used beyond the input itself.

Speed is not the only cost of an algorithm. A solution can be fast but still fail because it stores too much data.

Core Idea

Extra space includes helper arrays, dictionaries, sets, queues, stacks, recursion call frames, and tables. A function that only uses a few variables usually uses O(1) extra space. A function that stores one entry per input element usually uses O(n) extra space.

Some analyses include the input and output memory. In algorithm practice, “space complexity” often means auxiliary space unless the problem states otherwise.

The word “extra” matters. If a function receives a list of n values and only scans it, the input list already exists. The algorithm’s auxiliary space may still be O(1). If the function builds a set containing the same values, the extra space becomes O(n).

Memory can buy speed. A hash set may reduce time from O(n^2) to O(n), but it uses extra memory. Dynamic programming often trades memory for avoiding repeated recursion.

Example Contracts

unique_values(values) accepts an iterable of hashable values and returns a set containing the distinct values. Its extra memory grows with the number of distinct values.

total(values) accepts numeric values and returns their sum. It keeps only one running total, so its extra space is constant.

countdown(n) accepts a non-negative integer and prints values through recursive calls. The call stack grows with n, even though no explicit list is created.

Python Example

def unique_values(values):
    seen = set()
 
    for value in values:
        seen.add(value)
 
    return seen

The set may store up to n different values, so the extra space is O(n).

Compare it with this function:

def total(values):
    running = 0
    for value in values:
        running += value
    return running

This function uses one extra variable no matter how long values is, so its auxiliary space is O(1).

Hidden Space

Python code can allocate memory in places that are easy to miss:

first_half = values[:len(values) // 2]

This slice creates a new list. If the slice contains about half the input, it uses O(n) extra space.

Recursive calls also use stack frames:

def countdown(n):
    if n == 0:
        return
    countdown(n - 1)

This recursion has depth n, so it uses O(n) call-stack space.

Common Confusions

Using Python built-ins does not make memory disappear. A set, dict, list slice, queue, heap, or memoization cache still occupies memory.

Recursion also uses space. Even if the code does not create a visible list or dictionary, each active recursive call needs a stack frame.

Output space is a separate question. If the problem asks the algorithm to return a list of all answers, that output may be O(n) or larger. Some analyses count it, and some focus only on auxiliary space. State the convention when it matters.

When To Use It

Use space complexity when memory limits matter, when choosing between storing precomputed information and recomputing it, or when deciding whether recursion depth could become too large.

Also use it when comparing two approaches with the same time complexity. A solution that uses O(1) extra space may be preferable to one that uses O(n), unless the larger memory cost makes the code much simpler or faster.

The Main Point

Space complexity counts extra memory that grows with the input. Hidden storage such as sets, copied slices, result lists, and recursive call stacks matters.