What is Space Complexity?
What you'll learn: You'll discover how to measure the memory an algorithm consumes as input grows.
The Core Idea
When analyzing algorithms, we've focused heavily on time — how many operations an algorithm performs. But there's another critical resource: memory. Space complexity measures how much memory (RAM) an algorithm requires relative to the size of its input.
Just like we count operations for runtime analysis, we count memory usage. This includes:
- Variables you declare
- Arrays you create
- Function call stack space (from recursion)
- Any temporary data structures
The measurement is expressed using the same notations you've learned: Big-O, Big-Theta, and Big-Omega.
An Analogy
Imagine cooking a recipe (your algorithm) for n guests. Time complexity is how long it takes to cook. Space complexity is how much counter space and how many pots you need. A simple recipe might use just one bowl regardless of guest count (constant space). A complex recipe might need one pot per guest (linear space).
Examples in Plain English
- Swapping two variables: Uses a fixed amount of memory (a temporary variable) no matter the input size → O(1) space.
- Copying an array of size n: Requires space for the new array → O(n) space.
- Creating a 2D array of size n×n: Needs space for all n² elements → O(n²) space.
- Recursive factorial function: Each call uses stack memory, up to n calls deep → O(n) space for the call stack.
You analyze space the same way you analyze time: identify what memory grows with input size, find the dominant term, and drop constants.
Key Takeaway: Space complexity measures memory usage relative to input size, using the same Big-O family of notations you use for time complexity.