Python Space Complexity

Big O can describe memory the same way it describes time: how much extra space does the algorithm need as the input grows?

We count only the extra space — the variables and lists the algorithm creates — not the input itself. This extra space is called auxiliary space.

O(1) space: a fixed number of variables, no matter the input. O(n) space: something new is stored per input element, like a copy or a set of seen values.

An algorithm that keeps only a few plain variables uses constant space. The list can hold ten elements or ten million — the algorithm itself still owns just its counters.

Summing, finding the maximum, and linear search are all O(n) time but O(1) space: they read a lot and remember almost nothing.

The whole algorithm remembers exactly one number, total. Its memory use does not grow with the list: O(1) space.

As soon as the algorithm builds something with one entry per input element — a new list, a dictionary — its space is O(n): double the input, double the memory.

That is not bad by itself. It is simply a cost you should notice, because it can be traded.

The output list gets one element for every input element. 5 in, 5 out — memory grows in step with the input: O(n) space.

Often you can spend memory to save time. The classic example is Two Sum: find two numbers in a list that add up to a target.

The direct way checks every pair — O(n²) time, O(1) space. The fast way walks the list once and remembers every number it has seen in a set. For each number it asks: "have I already seen target - n?" — O(n) time, O(n) space.

This trade is usually worth it: memory can be added to a machine, time cannot.

Every pair is checked until a match appears — up to 15 checks for 6 elements, and the count grows with the square of the input. No extra memory is used.

One pass, 6 checks. Each number is looked up and stored in the seen set — constant-time work per element. The set is the O(n) memory that buys the O(n) time.