Foundations
Space Complexity Fundamentals
Difficulty: Beginner
An algorithm that runs in O(n) time but allocates a fresh array of size n^2 will not fit in memory long before it would have finished computing. Memory is finite, and many algorithms quietly trade it for speed; the only way to make that...
Space Complexity Fundamentals
An algorithm that runs in O(n) time but allocates a fresh array of size n^2 will not fit in memory long before it would have finished computing. Memory is finite, and many algorithms quietly trade it for speed; the only way to make that trade-off visible is to analyze space the same way you analyze time.
Space Complexity Fundamentals extends the Big-O lens from operation counting to memory usage. You will see why we draw a line between auxiliary space (the extra storage an algorithm allocates) and total space (auxiliary plus the input itself), and you will classify common algorithms as O(1) constant, O(n) linear, or O(n^2) quadratic in space. You will meet the in-place vs out-of-place distinction that interviewers love to probe, and you will study a first space-time trade-off where caching results turns repeated work into stored data.
In Big-O Notation (Upper Bound), you learned to read complexity classes from loop structure and to recognize that O(c * n) collapses to O(n). The same vocabulary and the same simplification rules apply here, but the resource being counted is bytes of allocated memory rather than units of work.
Once you can reason about both axes at once, you will be ready for Logarithms & Exponentiation, where you will build the mathematical intuition behind O(log n), the complexity class that powers binary search, balanced trees, and most efficient divide-and-conquer algorithms.
Prerequisites:
Big-O Notation (Upper Bound)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Define space complexity and distinguish it from time complexity.
Distinguish between auxiliary space and total space.
Identify common space complexities: O(1), O(n), O(n^2).
Explain the concept of in-place algorithms vs out-of-place algorithms.
Analyze simple space-time tradeoffs.
Why This Matters
01
Memory is a finite resource -- algorithms that use too much can crash or slow down due to swapping.
02
Many interview problems require O(1) extra space, and you need to recognize when that constraint applies.
03
Understanding space-time tradeoffs helps you choose the right algorithm for your constraints.
Key Terms
6 terms you'll encounter in this lesson
Space complexity
A measure of how much memory an algorithm uses as a function of input size, expressed in Big-O notation.
Auxiliary space
The extra memory an algorithm uses beyond the input itself. Also called 'extra space' or 'additional space'.
Total space
The total memory used by the algorithm, including the input. Total = input space + auxiliary space.
In-place algorithm
An algorithm that uses O(1) auxiliary space -- it modifies the input directly without creating significant extra data structures.
Out-of-place algorithm
An algorithm that creates a new data structure (e.g., a new array) to hold results, using O(n) or more auxiliary space.
Space-time tradeoff
Using more memory to reduce computation time, or using less memory at the cost of more computation.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Space complexity and time complexity are the same thing"
They measure different resources. Time = operations, Space = memory. An algorithm can be O(n) time and O(1) space, or O(n) time and O(n) space.
"The input does not count as space"
It depends on what you are measuring. Auxiliary space excludes the input. Total space includes it. Most discussions mean auxiliary space when they say 'space complexity'.
"In-place means the algorithm uses zero extra memory"
In-place means O(1) extra memory -- a constant amount. The algorithm still uses a few variables (counters, temp values), but the extra memory does not grow with input size.