Foundation · Module 1 · Lesson 3
Space complexity
Input space, auxiliary space, and recursion stacks.
Lesson 3 of 123
1d streakDetailed theory
Space complexity measures how memory usage grows with input size. In interviews, “space” usually means auxiliary space, but a complete analysis should say whether input, output, and recursion-stack memory are included.
By the end, you can
- Separate input space, output space, and auxiliary space.
- Count recursion-stack frames correctly.
- Compare in-place and copying approaches.
Vocabulary
Definitions with concrete meaning
Input space
Memory occupied by the data supplied to the algorithm.
Auxiliary space
Extra working memory allocated by the algorithm, excluding the input.
Output space
Memory required for the returned result. State whether it is counted, especially when output size is unavoidable.
Call-stack space
Memory for active recursive frames; it depends on maximum recursion depth.
Rules to apply
- 1Declare what your space figure includes; “O(1) auxiliary” is more precise than “O(1) space.”
- 2Count simultaneously live allocations, not total bytes ever allocated over time.
- 3A loop does not automatically use O(n) space; reused scalar variables remain O(1).
- 4A recursive function uses one frame per active level, even if it allocates no explicit collection.
- 5In-place usually means O(1) auxiliary space, though the input itself still occupies memory.
- 6An output-sensitive algorithm may need space proportional to the answer size.
Worked example 1
Reverse an array: copy versus in-place
Compare building a reversed array with swapping values inside the input.
- 1
Copying approach
Allocate n output slots and fill them in reverse order: Θ(n) auxiliary space.
- 2
In-place approach
Keep left, right, and temp; swap until pointers meet: Θ(1) auxiliary space.
- 3
State the trade-off
Both take Θ(n) time, but the in-place version mutates the input while the copy preserves it.
Space optimization can change semantics. “In-place” is not automatically the better API.
Worked example 2
Count recursive space
Merge sort recursively splits the array and uses a temporary merge buffer.
- 1
Recursion depth
Balanced splitting creates Θ(log n) active stack frames.
- 2
Merge storage
Temporary arrays total Θ(n) simultaneously at the dominant merge level.
- 3
Combine live memory
Θ(n) buffer + Θ(log n) stack = Θ(n) auxiliary space.
Add simultaneously live components, then keep the dominant term.
Comparison table
Time–space examples
The exact result can depend on implementation choices.
| Approach | Time | Auxiliary space | Important note |
|---|---|---|---|
| Iterative array reverse | Θ(n) | Θ(1) | Mutates input |
| Copying array reverse | Θ(n) | Θ(n) | Preserves input |
| Iterative binary search | Θ(log n) | Θ(1) | No call stack |
| Recursive binary search | Θ(log n) | Θ(log n) | One frame per level |
| Merge sort | Θ(n log n) | Θ(n) | Merge buffer dominates stack |
| BFS | Θ(V + E) | Θ(V) | Queue may hold a full frontier |
Check your understanding
1Does a loop that runs n times use Θ(n) auxiliary space?
Not necessarily. If each iteration reuses the same fixed variables, auxiliary space remains Θ(1).
2Why is recursive binary search not Θ(1) auxiliary space?
Its Θ(log n) active calls each occupy a stack frame.
3Can an algorithm be O(1) auxiliary space but return O(n) data?
Yes, when output storage is reported separately or required by the problem. State the convention clearly.
Cost Model
Complexity & Trade-offs
When to use it
- Working under memory limits or on large inputs.
- Choosing iterative versus recursive implementations.
- Evaluating in-place mutation, copying, caching, and streaming trade-offs.
Common mistakes
- Ignoring recursive call frames.
- Calling an algorithm O(1) space without saying “auxiliary.”
- Adding allocations that are never live at the same time or forgetting a dominant buffer.
Practice prompts
- Compare iterative and recursive binary-search space.
- Analyze DFS space on a chain and on a balanced tree.
- Explain the output-space cost of generating all permutations.
Mastery check