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.

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).

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.

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.