memory usage for n = 8

O(1)Constant — swap variables1 unit

O(log n)Logarithmic — recursive binary search3 units

O(n)Linear — copy of input array8 units

O(n²)Quadratic — 2D DP table64 units

Space complexity measures extra memory an algorithm uses as input grows.

Unlike time complexity, space only counts additional memory — not the input itself.

start

1 / 10

SPD0.5×

click to pause · hover for controls · fullscreen for more

Space Complexity

Watch memory grow — O(1), O(n), and O(n²) side by side

Visual by thisgirltech

BeginnerConcept

Space complexity measures how much extra memory an algorithm needs as a function of its input size n. Like time complexity, we express it using Big O notation and focus on how it scales, not the exact byte count.

Understanding space complexity is just as important as time complexity — a fast algorithm that runs out of memory is useless. The two often trade off: you can frequently gain speed by using more memory, and save memory by doing more work.

Auxiliary space

Space complexity typically refers to auxiliary space — the extra memory beyond the input itself, like variables, arrays, and call stacks.

Scales with n

The key question is: if input doubles, does memory stay flat, double, or quadruple? That's what O(1), O(n), and O(n²) answer.

Time-space tradeoff

Caching results (memoization) uses O(n) space to turn O(2ⁿ) time into O(n). Many optimizations work this way.

TIP

When reviewing code, always ask: what happens to memory if n is 10x larger? An O(n²) space algorithm that works for n=100 may crash at n=10,000.

COLOUR LEGEND

O(1) — constant

O(n) — linear

O(n²) — quadratic

O(n) stack depth