Space Complexity
A measure of the amount of memory an algorithm uses as a function of the length of the input.
Space Complexity
Space complexity is a measure of the amount of memory or storage space that an algorithm requires as a function of the input size. It quantifies how much additional memory the algorithm needs to complete its execution beyond the space needed to store the input.
When analyzing space complexity, we consider:
- Auxiliary space: The extra space used by the algorithm (excluding input size)
- Total space: The sum of auxiliary space and input size
Like time complexity, space complexity is typically expressed using Big O notation, representing the worst-case space usage. This helps us understand how an algorithm's memory requirements scale with larger inputs.
Space complexity considers various memory usages:
- Variables and constants
- Data structures (arrays, lists, stacks, etc.)
- Function call stack (especially important in recursive algorithms)
- Allocation of objects or structures during execution
An important concept related to space complexity is the distinction between "in-place" algorithms (which use O(1) auxiliary space) and algorithms that require significant additional space proportional to the input size.
Examples
- O(1) - Constant space: Algorithms that use a fixed amount of extra space regardless of input size (like iterative implementations of many algorithms)
- O(log n) - Logarithmic space: Often seen in recursive implementations of divide and conquer algorithms (the call stack uses logarithmic space)
- O(n) - Linear space: Algorithms that use extra space directly proportional to input size (like creating a new array of the same size)
- O(n²) - Quadratic space: Algorithms that create data structures with size proportional to n² (like adjacency matrices for graphs)
Related Terms
Big O Notation
A mathematical notation that describes the limiting behavior of a function when the argument tends towards infinity.
Time Complexity
A measure of the amount of time an algorithm takes to complete as a function of the length of the input.
In-place Algorithm
Algorithms that transform input using minimal additional memory space.
Further Learning
Want to see these concepts in action?