Memory is also a resource
We often obsess over how fast code runs, but every algorithm also consumes memory. Space complexity describes how the extra memory used grows as the input size grows. It matters because a method that is fast on paper can still crash a machine if it allocates too much.
Auxiliary versus total space
Two notions appear constantly.
- Total space counts everything, including the memory holding the input itself.
- Auxiliary space counts only the extra memory the algorithm allocates beyond the input, such as temporary arrays, hash tables, or the call stack.
When people compare algorithms they usually mean auxiliary space, because the input is a fixed cost everyone pays.
What to count
Tally the structures that grow with input size.
- Arrays, lists, and hash maps you allocate.
- The depth of the recursion stack, since each pending call holds local variables.
- Bookkeeping like visited sets or memoization tables.
An algorithm that reuses a few fixed variables uses constant extra space, while one that copies the whole input into a new structure uses linear extra space.
Trading space for time
Memoization and lookup tables spend memory to avoid repeated work, a classic time for space trade.
Key idea
Space complexity tracks how extra memory scales with input, dominated by allocated structures and recursion depth, and is often traded against running time.