Space Complexity
Space complexity measures the amount of memory an algorithm uses as input size grows. It includes both the memory for the input itself and the extra memory (auxiliary space) needed by the algorithm.
Like time complexity, space complexity is expressed with Big O notation. Common space complexities:
O(1)– Constant space (no extra memory proportional to input).O(n)– Linear space (e.g., creating a copy of an array).O(n²)– Quadratic space (e.g., a 2D matrix).
Examples:
// O(1) space – only a few variables
int sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
// O(n) space – creates new array of same size
int[] copy = new int[arr.length];
for (int i = 0; i < arr.length; i++) copy[i] = arr[i];
// O(n²) space – 2D array
int[][] matrix = new int[n][n];
Recursive algorithms also use stack space. For example, a recursive Fibonacci without memoization has O(n) space due to the call stack.
Two Minute Drill
- Space complexity = memory usage as input grows.
- Big O notation also used for space.
- Auxiliary space excludes input storage.
- Common: O(1), O(n), O(n²).
- Recursive calls add stack space.
- Optimize both time and space for better algorithms.
Need more clarification?
Drop us an email at career@quipoinfotech.com