Space Complexity
In this page:
What is Space Complexity
Space complexity measures how much extra memory an algorithm needs as its input grows, expressed the same way as time complexity using Big O. It matters just as much as speed when you're working with large datasets or memory-constrained environments like embedded devices.
Example: What is Space Complexity
#include <iostream>
using namespace std;
int main() {
int n = 5;
int arr[5]; // extra memory grows with n: O(n) space
for (int i = 0; i < n; i++) arr[i] = i * i;
cout << "arr[4]: " << arr[4] << " (O(n) extra space)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int n = 5;
int[] arr = new int[n]; // extra memory grows with n: O(n) space
for (int i = 0; i < n; i++) arr[i] = i * i;
System.out.println("arr[4]: " + arr[4] + " (O(n) extra space)");
}
}n = 5
arr = [i * i for i in range(n)] # extra memory grows with n: O(n) space
print("arr[4]:", arr[4], "(O(n) extra space)")#include <stdio.h>
int main() {
int n = 5;
int arr[5]; /* O(n) extra space */
for (int i = 0; i < n; i++) arr[i] = i * i;
printf("arr[4]: %d (O(n) extra space)\n", arr[4]);
return 0;
}Login to try C/C++/Java code in the editor
Auxiliary Space
Auxiliary space is the extra memory an algorithm allocates beyond the input itself, such as a temporary array, a hash map, or recursion's call stack. Two algorithms that both run in O(n) time can differ hugely in auxiliary space, which is often the real deciding factor between them.
Example: Auxiliary Space
#include <iostream>
using namespace std;
int main() {
int input[] = {5, 3, 1, 4};
int n = 4;
int temp[4]; // auxiliary array beyond the input itself
for (int i = 0; i < n; i++) temp[i] = input[i] * 2;
cout << "temp[2]: " << temp[2] << " (auxiliary O(n) space)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] input = {5, 3, 1, 4};
int[] temp = new int[4]; // auxiliary array beyond the input itself
for (int i = 0; i < 4; i++) temp[i] = input[i] * 2;
System.out.println("temp[2]: " + temp[2] + " (auxiliary O(n) space)");
}
}input_arr = [5, 3, 1, 4]
temp = [x * 2 for x in input_arr] # auxiliary list beyond the input itself
print("temp[2]:", temp[2], "(auxiliary O(n) space)")#include <stdio.h>
int main() {
int input[] = {5, 3, 1, 4};
int temp[4]; /* auxiliary array beyond the input itself */
for (int i = 0; i < 4; i++) temp[i] = input[i] * 2;
printf("temp[2]: %d (auxiliary O(n) space)\n", temp[2]);
return 0;
}Login to try C/C++/Java code in the editor
Space in Loops
A loop that just tracks a running total, a counter, or a single swapped value uses O(1) constant space no matter how large the input is, because it never allocates new storage proportional to n. That's why in-place algorithms are prized when memory is tight.
Example: Space in Loops
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int total = 0; // just one variable: O(1) space, no matter arr size
for (int i = 0; i < 5; i++) total += arr[i];
cout << "Total: " << total << " (O(1) space)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int total = 0; // O(1) space, no matter arr size
for (int x : arr) total += x;
System.out.println("Total: " + total + " (O(1) space)");
}
}arr = [1, 2, 3, 4, 5]
total = 0 # O(1) space, no matter list size
for x in arr:
total += x
print("Total:", total, "(O(1) space)")#include <stdio.h>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int total = 0; /* O(1) space */
for (int i = 0; i < 5; i++) total += arr[i];
printf("Total: %d (O(1) space)\n", total);
return 0;
}Login to try C/C++/Java code in the editor
Recursion and Space
Every recursive call pushes a new frame onto the call stack to remember its local variables and where to return to, so a recursion that goes n levels deep uses O(n) space even if it does no other allocation. This is a common reason recursive solutions can hit stack overflow errors that their iterative equivalents wouldn't.
Example: Recursion and Space
#include <iostream>
using namespace std;
int sumTo(int n) {
if (n == 0) return 0; // each call stays on the stack: O(n) space
return n + sumTo(n - 1);
}
int main() {
cout << "sumTo(5): " << sumTo(5) << " (O(n) stack space)" << endl;
return 0;
}public class Main {
static int sumTo(int n) {
if (n == 0) return 0; // O(n) stack space
return n + sumTo(n - 1);
}
public static void main(String[] args) {
System.out.println("sumTo(5): " + sumTo(5) + " (O(n) stack space)");
}
}def sum_to(n):
if n == 0:
return 0 # O(n) stack space
return n + sum_to(n - 1)
print("sum_to(5):", sum_to(5), "(O(n) stack space)")#include <stdio.h>
int sumTo(int n) {
if (n == 0) return 0; /* O(n) stack space */
return n + sumTo(n - 1);
}
int main() {
printf("sumTo(5): %d (O(n) stack space)\n", sumTo(5));
return 0;
}Login to try C/C++/Java code in the editor
Memory Choices
Good algorithm design usually means trading time for space or vice versa: caching results can speed up an algorithm at the cost of memory, while an in-place approach saves memory but may need more careful, sometimes slower, logic. Recognizing this trade-off is a core DSA skill.
Example: Memory Choices
#include <iostream>
using namespace std;
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
// In-place swap: saves memory (O(1) space), no extra array needed.
for (int i = 0; i < n / 2; i++) {
int tmp = arr[i];
arr[i] = arr[n - 1 - i];
arr[n - 1 - i] = tmp;
}
cout << "Reversed[0]: " << arr[0] << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2};
int n = 4;
// In-place swap: O(1) space, no extra array needed.
for (int i = 0; i < n / 2; i++) {
int tmp = arr[i];
arr[i] = arr[n - 1 - i];
arr[n - 1 - i] = tmp;
}
System.out.println("Reversed[0]: " + arr[0]);
}
}arr = [5, 1, 4, 2]
arr.reverse() # in-place: O(1) extra space, no new list built
print("Reversed[0]:", arr[0])#include <stdio.h>
int main() {
int arr[] = {5, 1, 4, 2};
int n = 4;
/* In-place swap: O(1) space, no extra array needed. */
for (int i = 0; i < n / 2; i++) {
int tmp = arr[i];
arr[i] = arr[n - 1 - i];
arr[n - 1 - i] = tmp;
}
printf("Reversed[0]: %d\n", arr[0]);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 6 topics to unlock
0/6 topics done
Complete these topics first: