Topic 48 of 78
Big O Space Complexity
Overview
While Time Complexity measures how long an algorithm takes, Space Complexity measures how much extra memory (RAM) an algorithm requires as the input size grows. If you duplicate an array of N elements to process it, your space complexity is O(N). In modern systems, memory is cheaper than CPU cycles, but a strict O(1) space requirement is a common interview constraint to test if you can manipulate pointers in-place.
Syntax
In-place modifications (like reversing an array with two pointers) achieve O(1) space, which is highly prized in systems with limited memory.
Common Space Complexities
java
// O(1) - Constant Space: Using a fixed number of variables
int sum = 0;
for (int i : arr) sum += i;
// O(N) - Linear Space: Memory scales 1:1 with input size
int[] copy = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
copy[i] = arr[i];
}
// O(log N) Space: Usually the result of the Recursion Call Stack
// in algorithms like Quick Sort or Tree traversals.Common Pitfalls
- Forgetting that recursive function calls consume memory on the Call Stack. Depth of recursion = Space Complexity.
- Creating new Strings inside a loop (which creates new memory objects in Java) instead of using an O(N) StringBuilder.
Interview Tips
- The memory taken by the input array itself does NOT count towards Space Complexity. Only the EXTRA memory you allocate counts.
Real-World Example
Embedded systems (like an Apple Watch or an IoT device) have strictly limited RAM. Algorithms running on these devices must heavily prioritize O(1) space complexity.
example
java
// O(N) Space approach
public void reverse(int[] arr) {
int[] temp = new int[arr.length];
// ... copy backwards ...
}
// O(1) Space approach (Preferred for IoT)
public void reverseInPlace(int[] arr) {
int left = 0, right = arr.length - 1;
while(left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++; right--;
}
}