space complexity
How the extra memory an algorithm needs grows with the input size, written in the same Big O notation as time.
In more detail
A function that builds a reversed copy of a list needs O(n) extra space, while one that swaps items in place needs O(1). Recursion also uses space, one stack frame per active call. Time and space often trade against each other, as when a cache spends memory to save repeated work.
Related terms
- auxiliary space — The memory an algorithm allocates beyond the input itself, such as a temporary copy or a helper array.
- in-place algorithm — An algorithm that rearranges its input within the input's own memory, using only a constant amount of extra space.
- call stack — The region of memory where a running program keeps one frame for each function call that has started but not yet returned.
- time complexity — A description of how the amount of work an algorithm does grows as its input gets bigger.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers