Space Complexity: Memory Optimization in Python
Space complexity matters as much as time. An algorithm that runs in milliseconds but uses gigabytes of RAM will crash your server or laptop. Python's memory management can hide space problems until they suddenly fail. This tutorial teaches you to analyze space complexity, measure real memory usage, and apply practical techniques to minimize it.
What Is Space Complexity?
Space complexity measures how much extra memory an algorithm uses relative to input size. It excludes the input itself and counts only temporary data structures and function call stacks. An O(1) space algorithm uses roughly the same memory regardless of input size. An O(n) algorithm allocates space proportional to input.
Analyzing Space Complexity
O(1) Space — Constant Memory
Algorithms that modify data in place use O(1) extra space:
# O(1) space — modifies array in place
def reverse_in_place(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
arr = [1, 2, 3, 4, 5]
reverse_in_place(arr)
print(arr) # [5, 4, 3, 2, 1]
No extra data structures are allocated. Only a fixed number of variables (left, right) exist regardless of input size. Space used: O(1).
O(n) Space — Linear Memory
Algorithms that create new data structures proportional to input use O(n) space:
# O(n) space — creates a new list
def reverse_with_copy(arr):
return arr[::-1] # creates a new list of size n
# O(n) space — list comprehension allocates new list
def square_numbers(numbers):
return [x**2 for x in numbers]
Each line creates a new data structure with n elements. Space used: O(n).
O(n log n) Space — Recursive Call Stack
Recursive algorithms accumulate stack frames. Merge sort uses O(log n) extra space for call frames plus O(n) for temporary arrays:
# O(n log n) space total — O(n) for temporary arrays, O(log n) for call stack
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # recursive call adds stack frame
right = merge_sort(arr[mid:]) # recursive call adds stack frame
return merge(left, right) # creates temporary arrays
The call stack has depth O(log n) because each call halves the problem. Combined with the temporary arrays used in merge(), total space is O(n log n).
O(n²) Space — Nested Data Structures
Creating nested structures multiplies space:
# O(n²) space — creates n lists, each of size n
def create_matrix(n):
return [[0 for _ in range(n)] for _ in range(n)]
matrix = create_matrix(1000) # allocates 1 million integers = ~4 MB
A 1000×1000 matrix uses 1 million elements. A 10,000×10,000 matrix uses 100 million elements and ~400 MB of RAM. This quadratic growth quickly consumes memory.
Measuring Memory Usage
Use memory_profiler to see actual memory consumption line by line:
from memory_profiler import profile
@profile
def test_memory():
small_list = [i for i in range(100000)] # allocates list
print("Created list")
big_list = [i for i in range(1000000)] # allocates bigger list
print("Created big list")
return big_list
test_memory()
Run with python -m memory_profiler your_script.py to see line-by-line memory growth:
Line # Mem usage Increment Line Contents
4 11.2 MiB 0.0 MiB def test_memory():
5 12.2 MiB 1.0 MiB small_list = [i for i in range(100000)]
6 12.2 MiB 0.0 MiB print("Created list")
7 20.0 MiB 7.8 MiB big_list = [i for i in range(1000000)]
8 20.0 MiB 0.0 MiB print("Created big list")
This shows exactly which lines allocate memory. Use it to identify surprises.
Technique 1: Use Generators Instead of Lists
Generators compute values on-demand (lazy evaluation) instead of storing all values in memory:
# O(n) space — creates list with all numbers
def get_numbers_as_list(n):
return [i for i in range(n)]
# O(1) space — computes one number at a time
def get_numbers_as_generator(n):
for i in range(n):
yield i
# Test memory difference
list_result = get_numbers_as_list(1000000) # allocates 1 million integers
gen_result = get_numbers_as_generator(1000000) # allocates nothing
# Iterate—only one value in memory at a time
for num in gen_result:
process(num) # 'num' is the only integer stored
The generator version never stores the full list. It computes and yields one value at a time. For large datasets, this is a massive saving.
Generator Patterns
Use generators for filtering and transforming:
# O(n) space — materializes entire result
def filter_large_files(filenames):
return [f for f in filenames if should_process(f)]
# O(1) space — yields filenames one at a time
def filter_large_files_lazy(filenames):
for f in filenames:
if should_process(f):
yield f
# Use in processing
for filename in filter_large_files_lazy(million_filenames):
process_file(filename) # only one filename in memory
Technique 2: In-Place Algorithms
Modify data without creating copies:
# O(n) space — creates new lists
def sort_and_filter_copy(arr):
sorted_arr = sorted(arr) # creates copy
result = [x for x in sorted_arr if x > 10] # creates another copy
return result
# O(1) space — modifies original, no extra structures
def sort_and_filter_inplace(arr):
arr.sort() # sorts in place, O(1) extra space
# Filter in place by building from left
write_idx = 0
for read_idx in range(len(arr)):
if arr[read_idx] > 10:
arr[write_idx] = arr[read_idx]
write_idx += 1
return arr[:write_idx] # only creates one small copy for return
The in-place version modifies the original array and avoids intermediate allocations. This is critical for processing gigabyte-sized datasets.
Technique 3: Stream Processing Large Files
Never load entire files into memory:
# O(n) space — bad, loads entire file
def sum_large_file_BAD(filepath):
with open(filepath) as f:
all_lines = f.readlines() # allocates gigabytes if file is huge
return sum(int(line) for line in all_lines)
# O(1) space — good, processes line by line
def sum_large_file_GOOD(filepath):
total = 0
with open(filepath) as f:
for line in f: # yields one line at a time
total += int(line)
return total
File iteration (when you don't call readlines()) yields one line at a time. Your loop only stores one line and the running total.
Processing CSV/JSON Streams
import json
# O(n) space — loads entire JSON array
def process_json_bad(filepath):
with open(filepath) as f:
data = json.load(f) # all records in memory
for record in data:
process_record(record)
# O(1) space — reads one JSON object per line
def process_json_good(filepath):
with open(filepath) as f:
for line in f:
record = json.loads(line) # parses one line
process_record(record)
The second version is practical for millions of records.
Technique 4: Detect and Fix Memory Leaks
Memory leaks in Python are usually from unintended references keeping objects alive:
# Memory leak — global cache grows unbounded
_cache = {}
def process_item(item_id, data):
_cache[item_id] = data # keeps growing
return _cache[item_id]
# Fix: use bounded cache with LRU eviction
from functools import lru_cache
@lru_cache(maxsize=10000)
def process_item_fixed(item_id, data):
return data
LRU cache (covered in a later article) automatically evicts old entries when size exceeds maxsize. This prevents unbounded growth.
Finding Leaks with objgraph
import objgraph
# Find unreferenced objects taking memory
objgraph.show_most_common_types(limit=10)
# Get a diff before and after suspicious operation
objgraph.show_growth()
do_suspicious_operation()
objgraph.show_growth()
This shows which object types are being created and not released.
Memory Profiling in Production
For production environments, use lightweight tools:
import psutil
import os
def get_memory_usage():
process = psutil.Process(os.getpid())
return process.memory_info().rss / 1024 / 1024 # MB
print(f"Memory before: {get_memory_usage():.1f} MB")
result = process_large_dataset()
print(f"Memory after: {get_memory_usage():.1f} MB")
Track memory at key points without overhead. psutil adds minimal latency.
Key Takeaways
- Space complexity describes extra memory used relative to input size
- O(1) space algorithms modify in place; O(n) space algorithms allocate proportional structures
- Generators use O(1) space by computing values on demand instead of storing lists
- Stream processing (line-by-line file iteration) avoids loading entire files into memory
- In-place algorithms avoid creating copies and intermediate data structures
- Use
memory_profilerto measure line-by-line memory usage and find surprises
Frequently Asked Questions
When is O(n) space acceptable?
When your input is O(n) and you must return O(n) results, allocating O(n) space is unavoidable. The concern is extra space beyond input and output. If you sort data and return the sorted copy, O(n) space is acceptable. If you're storing redundant copies or building unbounded caches, that's waste.
Does Python garbage collection automatically prevent memory leaks?
Mostly, but not entirely. Garbage collection frees objects with zero references. If you intentionally or accidentally keep a reference (like a global cache or circular reference), the object survives. The GC is excellent but not a substitute for careful design.
Should I always use generators?
Generators are powerful for large datasets but add complexity. For small lists (< 10,000 items), the overhead of generators might exceed the benefit. Use generators for streaming data, file processing, and very large datasets. Use lists for collections you'll iterate multiple times.
How much memory does a Python list item really use?
A Python list stores pointers (8 bytes on 64-bit systems) to Python objects. An integer object itself is ~28 bytes overhead. So a list of 1 million integers uses roughly 8MB (pointers) plus 28MB (integer objects) = 36MB. This is why storing primitives in NumPy arrays (8 bytes per int without Python overhead) is more efficient.
What's the difference between RSS and VMS memory metrics?
RSS (resident set size) is physical RAM currently used. VMS (virtual memory size) includes disk swap. For Python performance, watch RSS. High VMS with low RSS means Python has allocated memory but isn't actively using it (yet).