What Is Space Complexity? A Beginner's Guide with Examples
- Space complexity describes how an algorithm's memory usage grows with input size, expressed in Big-O notation.
- Auxiliary space is what interviews actually test — extra memory beyond the input, not the input itself.
- O(1) uses fixed variables; O(n) appears with hash maps and arrays; O(n²) shows up in 2D dynamic programming tables.
- Recursion has a hidden cost: every call frame counts, making an unbalanced DFS O(n) stack depth even with no extra data structures.
- The time-space tradeoff is a design decision — hash maps buy O(n) time at the cost of O(n) memory over an O(n²) brute-force approach.
- Always state space complexity after time complexity in interviews; one sentence naming what consumes the memory is enough to score the dimension.
You nail the time complexity analysis. You explain the O(n log n) sort, the O(1) lookup, the tradeoff between the nested loop and the hash map. You're on a roll. The interviewer nods.
Then: "What about the space complexity?"
And you pause.
Not a thoughtful pause. The kind where your brain switches to buffering mode and you can hear your own heartbeat. Space complexity is the thing every prep resource covers in two sentences after spending ten paragraphs on Big-O. This post is those ten paragraphs.
Memory Usage Grows. The Question Is How Fast.
Space complexity describes how an algorithm's memory consumption scales as its input grows. Same Big-O notation you already know, just pointed at a different resource. An algorithm that uses a fixed amount of memory regardless of input size is O(1). One that stores a copy of the entire input is O(n). One that builds an n-by-n table is O(n²) and deserves a moment of silence.
The core question: if you double the input, what happens to memory? Does it stay flat? Double? Quietly spiral until your program gets killed by the OS?
Here's a concrete anchor. You have a list of a million integers. If your algorithm only needs a couple of extra variables (a counter, a running sum), it uses O(1) extra space regardless of how long the list is. If it creates a new list of the same length, that's O(n). If it builds a grid for every pair of elements, that's O(n²). The input is fixed. What varies is what your code builds on top of it.
For deeper background on Big-O notation itself, see Big-O Notation: How to Read Any Loop and Know Its Complexity.
Auxiliary Space vs Total Space
Total space complexity includes the input itself. Auxiliary space complexity counts only the extra memory your algorithm allocates beyond the input. In interviews, when someone says "this solution uses O(1) space," they almost always mean O(1) auxiliary space. The input has to live somewhere regardless of what you do with it.
Why does the distinction matter? The problem statement forces you to accept an O(n) input. The real question is whether your algorithm can operate on top of it without proportionally more memory. Reversing an array in-place is O(1) auxiliary space. Building a reversed copy is O(n). Both are correct programs. Only one passes the space constraint.
Unless an interviewer specifies otherwise, assume they're asking about auxiliary space. That's the number you actually control.
The Four Classes You'll Actually See
O(1), Constant Space
Fixed memory, always. Doesn't matter if the input has ten elements or ten million. The amount of extra space your code uses stays the same.
def sum_array(nums: list[int]) -> int: total = 0 for n in nums: total += n return total
Two extra variables: total and n. That's it. The list can be arbitrarily long and these two variables don't multiply. O(1).
O(log n), Logarithmic Space
This shows up in recursive algorithms that halve the problem at each step. Binary search done recursively consumes O(log n) stack frames because the recursion depth equals the number of times you can halve n before hitting 1.
def binary_search(nums: list[int], target: int, low: int, high: int) -> int: if low > high: return -1 mid = (low + high) // 2 if nums[mid] == target: return mid if nums[mid] < target: return binary_search(nums, target, mid + 1, high) return binary_search(nums, target, low, mid - 1)
The array doesn't grow. But each recursive call pushes a frame onto the call stack, and you make at most log₂(n) calls before terminating. Space: O(log n).
O(n), Linear Space
Memory proportional to input size. Hash maps and auxiliary arrays are the usual suspects.
def two_sum(nums: list[int], target: int) -> list[int]: seen = {} for index, value in enumerate(nums): complement = target - value if complement in seen: return [seen[complement], index] seen[value] = index return []
The seen hash map can grow to hold every element in nums. Worst case: you scan the whole array without finding a pair and seen now has n entries. Space: O(n).
This is the most common tradeoff in interviews. Two pointers can solve many of the same problems with O(1) extra space. The hash map trades memory for speed. Both are valid answers. Know which trade you're making and be ready to say so.
O(n²), Quadratic Space
Appears when you build a 2D table. This happens constantly in dynamic programming solutions for string problems.
def longest_common_subsequence(text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]
The dp table has (m+1) × (n+1) cells. If both strings have length n, that's O(n²) space. Many DP problems can be compressed to O(n) by keeping only the previous row, but the full table is where most people land first.
Recursion Quietly Eats the Call Stack
This is the one that gets people. Every recursive call pushes a frame onto the call stack, and those frames pile up until the deepest call returns. There are no hash maps. No auxiliary arrays. Nothing obvious. The space just evaporates.
For a tree traversal, the call stack depth equals the tree height. A balanced binary tree of n nodes gives you O(log n) depth. A skewed tree (essentially a linked list dressed up in tree clothes) gives you O(n). Neither shows up as a declaration in your code.
def depth_first_search(node): if node is None: return process(node) depth_first_search(node.left) depth_first_search(node.right)
No extra data structures anywhere. Still O(h) space where h is the tree height. The call stack is the data structure. It's just the one you can't see.
The same trap appears in linear recursion. Recursive factorial on input n pushes n frames before it starts returning:
def factorial(n: int) -> int: if n <= 1: return 1 return n * factorial(n - 1)
Space: O(n). Not O(1), despite the total absence of extra variables. The recursion chain is the memory.
Your "elegant" recursive solution, encountering a sufficiently large input
This matters in practice. Python's default recursion limit is 1,000 frames. Linux and macOS main threads get 8MB of stack space. Hit either limit on a large enough input and your program crashes before it ever produces a wrong answer. Space complexity is the warning you skipped.
For a thorough treatment, see Recursion Space Complexity: Your Stack Only Holds One Path at a Time and Stack vs Heap: The Two Memory Regions Behind Every Recursion Bug.
The Time-Space Tradeoff Is a Design Decision
Most performance improvements in algorithms come from spending memory to save time. This is not a coincidence. It's the fundamental shape of the deal.
You pay in space to save time, and the interview question is whether that trade makes sense given the constraints.
Two sum with a nested loop is O(n²) time and O(1) space. Two sum with a hash map is O(n) time and O(n) space. Both correct. Prefix sums are the same logic: precompute O(n) cumulative values once, then answer every range query in O(1) instead of scanning the subarray each time.
def build_prefix_sum(nums: list[int]) -> list[int]: prefix = [0] * (len(nums) + 1) for i, value in enumerate(nums): prefix[i + 1] = prefix[i] + value return prefix def range_sum(prefix: list[int], left: int, right: int) -> int: return prefix[right + 1] - prefix[left]
You spend O(n) memory upfront. Every query after that is free. Answering a thousand queries on the same array? Obviously worth it. Answering one query on an enormous dataset with tight memory constraints? Maybe not.
Knowing your space complexity means you can have that conversation instead of guessing at what the interviewer wants.
For more, see The Time-Space Tradeoff: When Storing More Makes Code Faster and Time and Space Complexity: The Two Costs Behind Every Algorithm.
How Interviewers Actually Ask About Space
Interviewers rarely say "state the space complexity" and wait. They probe sideways.
"Can you solve this without extra space?" means O(1) auxiliary. "What are the memory implications of your approach?" means reason about growth. "Could we do this with a rolling array instead?" means you missed an optimization and they're pointing you at it.
If you never mention space complexity unprompted, you're leaving a scoring dimension untouched. After walking through time complexity, add space immediately. One sentence: "This uses O(n) auxiliary space for the hash map." Then, if a leaner approach exists, name it even if you're sticking with the current solution for clarity.
The complete version sounds like this: state the complexity class, name what's consuming the space (the hash map, the call stack, the DP table), and say whether a more efficient alternative exists and what it would cost in time. Ten seconds. Three points. It signals that you think about both dimensions automatically, without needing to be asked.
If you want to practice saying all of this out loud under pressure, SpaceComplexity runs voice-based mock interviews where you're expected to walk through the full analysis, not just produce code that compiles.
Key Takeaways
- Space complexity measures how memory usage grows with input size, expressed in Big-O.
- Interviews almost always mean auxiliary space (excluding the input itself).
- O(1) is fixed memory; O(log n) comes from recursive halving; O(n) from structures that scale with input; O(n²) from 2D tables.
- Recursion has a hidden cost. The call stack depth equals the recursion depth, not zero.
- Most time improvements trade space, and most space improvements trade time. Name the tradeoff explicitly.
- Always state space complexity after time complexity. One sentence is enough.