Space Complexity Analysis
This guide covers space complexity analysis, memory usage patterns, and how to analyze algorithm memory efficiency across different programming languages.
🎯 What is Space Complexity?
Space complexity measures how the memory usage of an algorithm grows as the input size increases. It helps us understand memory requirements and optimize for memory-constrained environments.
Space Complexity Notation
- O(1): Constant space - memory usage doesn't depend on input size
- O(log n): Logarithmic space - grows very slowly
- O(n): Linear space - grows proportionally with input size
- O(n log n): Linearithmic space - common in efficient sorting
- O(n²): Quadratic space - grows quickly, common in nested data structures
🔧 Space Complexity Examples
O(1) - Constant Space
Temporary Variables
Using a few additional variables (like a temp for swapping or a counter for a loop) consumes a fixed amount of memory regardless of the input size. This is the definition of O(1) space complexity.
# Swapping two variables
def swap(a, b):
temp = a # One extra variable
a = b
b = temp
return a, b
# Finding maximum
def find_max(arr):
max_val = arr[0] # One extra variable
for num in arr:
if num > max_val:
max_val = num
return max_val
O(n) - Linear Space
# Creating a copy of array
def reverse_array(arr):
reversed_arr = [] # O(n) space
for i in range(len(arr)-1, -1, -1):
reversed_arr.append(arr[i])
return reversed_arr
# Recursive factorial (call stack)
def factorial(n):
if n <= 1:
return 1
return n * factorial(n-1) # O(n) call stack space
O(n²) - Quadratic Space
# Creating all pairs
def all_pairs(arr):
pairs = [] # O(n²) space
for i in range(len(arr)):
for j in range(i+1, len(arr)):
pairs.append((arr[i], arr[j]))
return pairs
# Adjacency matrix for graph
def create_adjacency_matrix(n):
matrix = [[0] * n for _ in range(n)] # O(n²) space
return matrix
📊 Memory Usage Comparison
| Input Size | O(1) | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|---|
| 10 | 1 | 4 | 10 | 33 | 100 |
| 100 | 1 | 7 | 100 | 664 | 10,000 |
| 1,000 | 1 | 10 | 1,000 | 9,966 | 1,000,000 |
| 10,000 | 1 | 13 | 10,000 | 132,877 | 100,000,000 |
🎯 Language-Specific Memory Analysis
Java Memory
// Primitive types - fixed size
int num = 42; // 4 bytes
double value = 3.14; // 8 bytes
boolean flag = true; // 1 byte
// Objects - overhead + fields
String str = "Hello"; // ~12 bytes + overhead
ArrayList<Integer> list = new ArrayList<>(); // Dynamic, grows as needed
// Memory estimation
public class MemoryExample {
public static void main(String[] args) {
Runtime runtime = Runtime.getRuntime();
long usedMemory = runtime.totalMemory() - runtime.freeMemory();
int[] array = new int[1000000]; // ~4MB
long newUsedMemory = runtime.totalMemory() - runtime.freeMemory();
System.out.println("Memory used: " + (newUsedMemory - usedMemory) + " bytes");
}
}
Python Memory
import sys
# Check object size
def get_size(obj):
return sys.getsizeof(obj)
# Lists have overhead
my_list = [1, 2, 3, 4, 5]
print(f"List size: {get_size(my_list)} bytes") # ~120 bytes
# Dictionaries have more overhead
my_dict = {"a": 1, "b": 2, "c": 3}
print(f"Dict size: {get_size(my_dict)} bytes") # ~360 bytes
# Strings are objects
my_string = "Hello, World!"
print(f"String size: {get_size(my_string)} bytes") # ~50 bytes
C Memory
#include <stdio.h>
#include <stdlib.h>
// Manual memory management
int* create_array(int size) {
int* array = (int*)malloc(size * sizeof(int));
if (array == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
return array;
}
// Memory usage tracking
void check_memory_usage() {
// Platform-specific memory checking
#ifdef __linux__
FILE* status = fopen("/proc/self/status", "r");
// Parse memory information
fclose(status);
#endif
}
🚀 Memory Optimization Strategies
In-Place Operations
# Bad: O(n) extra space
def reverse_array_extra(arr):
reversed_arr = [] # O(n) space
for i in range(len(arr)-1, -1, -1):
reversed_arr.append(arr[i])
return reversed_arr
# Good: O(1) extra space
def reverse_array_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
Generator Usage
# Bad: O(n) space for large dataset
def process_large_file_bad(filename):
with open(filename, 'r') as file:
lines = file.readlines() # Loads entire file
return [line.strip() for line in lines]
# Good: O(1) space using generator
def process_large_file_good(filename):
with open(filename, 'r') as file:
for line in file: # Process one line at a time
yield line.strip() # Generator, memory efficient
Memory Pool Pattern
// Bad: Creating many objects
public class BadExample {
public void processItems(List<Item> items) {
for (Item item : items) {
ProcessedItem processed = new ProcessedItem(item); // Many objects
process(processed);
}
}
}
// Good: Reusing objects
public class GoodExample {
private ProcessedItem reusableItem = new ProcessedItem();
public void processItems(List<Item> items) {
for (Item item : items) {
reusableItem.reset(item); // Reuse object
process(reusableItem);
}
}
}
Efficient Data Structures
# Bad: List for frequent lookups
user_permissions_list = [("alice", ["read", "write"]), ("bob", ["read"])]
def has_permission(username, permission):
for user, perms in user_permissions_list: # O(n)
if user == username:
return permission in perms
return False
# Good: Dictionary for O(1) lookups
user_permissions_dict = {
"alice": {"read", "write"},
"bob": {"read"}
}
def has_permission_optimized(username, permission):
return permission in user_permissions_dict.get(username, set()) # O(1)
🛠️ Memory Profiling
Java Profiling
// Using VisualVM or JConsole
// 1. Run application with: java -XX:+PrintGCDetails -XX:+PrintGCTimeStamps
// 2. Connect VisualVM: jvisualvm
// 3. Monitor heap usage, garbage collection, and object creation
// Programmatic memory checking
public class MemoryProfiler {
public static void logMemoryUsage(String label) {
Runtime runtime = Runtime.getRuntime();
long totalMemory = runtime.totalMemory();
long freeMemory = runtime.freeMemory();
long usedMemory = totalMemory - freeMemory;
System.out.println(label + ": " + (usedMemory / 1024 / 1024) + " MB");
}
}
Python Profiling
import tracemalloc
import sys
# Memory tracing
tracemalloc.start()
# Your code here
def memory_intensive_function():
large_list = [i for i in range(1000000)]
return sum(large_list)
result = memory_intensive_function()
# Get memory statistics
current, peak = tracemalloc.get_traced_memory()
print(f"Current memory usage: {current / 1024 / 1024:.2f} MB")
print(f"Peak memory usage: {peak / 1024 / 1024:.2f} MB")
# Get top memory consumers
snapshot = tracemalloc.take_snapshot()
top_stats = snapshot.statistics('lineno')
for stat in top_stats[:10]:
print(stat)
C Memory Debugging
# Using Valgrind
gcc -g program.c -o program
valgrind --tool=memcheck --leak-check=full ./program
# Using AddressSanitizer
gcc -fsanitize=address -g program.c -o program
./program
# Memory leak detection
# In code:
#include <stdlib.h>
void* safe_malloc(size_t size) {
void* ptr = malloc(size);
if (ptr == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
printf("Allocated %zu bytes at %p\n", size, ptr);
return ptr;
}
void safe_free(void* ptr) {
if (ptr != NULL) {
printf("Freeing memory at %p\n", ptr);
free(ptr);
}
}
📈 Memory Optimization Patterns
Lazy Loading
# Bad: Load everything upfront
class BadDataLoader:
def __init__(self):
self.all_data = self.load_all_data() # Loads everything
def get_user(self, user_id):
return self.all_data[user_id]
# Good: Load on demand
class GoodDataLoader:
def __init__(self):
self.cache = {}
def get_user(self, user_id):
if user_id not in self.cache:
self.cache[user_id] = self.load_user(user_id) # Load only when needed
return self.cache[user_id]
Memory-Mapped Files
// For large files, use memory mapping
#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
void* map_file(const char* filename, size_t* size) {
int fd = open(filename, O_RDONLY);
if (fd == -1) return NULL;
struct stat sb;
if (fstat(fd, &sb) == -1) return NULL;
*size = sb.st_size;
void* mapped = mmap(NULL, *size, PROT_READ, MAP_PRIVATE, fd, 0);
close(fd);
return mapped; // File mapped into memory
}
Streaming Processing
# Process large datasets without loading everything
def process_large_dataset(filename):
with open(filename, 'r') as file:
for line in file: # Process one line at a time
data = parse_line(line)
if meets_criteria(data):
yield process_data(data) # Generator, memory efficient
# Usage
for result in process_large_dataset("large_file.txt"):
handle_result(result)
🧪 Practice Problems
Easy
- Space Analysis: What is the space complexity of reversing a string in-place?
- Memory Usage: How much memory does storing 1 million integers require?
- Optimization: Convert O(n²) space algorithm to O(n) space.
Medium
- In-Place Operations: Implement in-place quicksort and analyze its space complexity.
- Memory Pool: Design a memory pool for frequent object allocation/deallocation.
- Streaming: Process a large CSV file without loading it entirely into memory.
Hard
- External Sorting: Design an algorithm to sort data that doesn't fit in memory.
- Memory Mapping: Implement file processing using memory-mapped I/O.
- Garbage Collection: Analyze memory usage patterns and optimize for GC efficiency.
📚 Related Resources
- Memory Management in Java - Official Java memory guide
- Python Memory Management - Python memory documentation
- C Memory Management - GNU C memory guide
🔗 Related Guides
- Time Complexity - Runtime analysis
- Algorithm Analysis - Comprehensive analysis techniques
- Optimization Techniques - Performance improvement strategies
- Benchmarking Methods - Measuring actual performance
🔗 Language-Specific Memory
- Java Performance Tips - Java memory optimization
- Python Performance Tips - Python memory optimization
- C Performance Tips - C memory management
- Oracle Performance Tips - Oracle memory optimization