space complexity
Space complexity measures how much memory an algorithm needs as the size of its input grows. Like time complexity, it counts memory by growth rate rather than exact bytes, so the measure stays independent of any particular machine.
The figure usually splits into the space taken up by the input itself and the auxiliary space an algorithm allocates while it runs, which gives two parts:
Many analyses report only the auxiliary space, since that is the part the algorithm controls.
The result is written in Big O notation, so an in-place routine that reuses a fixed number of variables runs in O(1) space, while one that builds a fresh copy of its input runs in O(n) space.
Space frequently trades off against speed. Caching and memoization store computed results to save time at the cost of higher memory use, and a deeply recursive routine consumes stack space that an iterative version avoids. Weighing space against running time is a routine part of choosing an algorithm in memory-constrained settings.
Related Resources
Tutorial
Sorting Algorithms in Python
In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.
For additional information on related topics, take a look at the following resources:
- Memory Management in Python (Tutorial)
- Recursion in Python: An Introduction (Tutorial)
- Caching in Python Using the LRU Cache Strategy (Tutorial)
- Thinking Recursively in Python (Tutorial)
- Introduction to Sorting Algorithms in Python (Course)
- How Python Manages Memory (Course)
- Memory Management in Python (Quiz)
- Recursion in Python (Course)
- Recursion in Python: An Introduction (Quiz)
- Caching in Python With lru_cache (Course)
- Thinking Recursively With Python (Course)
