10.3 Space complexity

Space complexity analyzes how much memory an algorithm uses as input size grows. Alongside time complexity, it gives you a full picture of an algorithm's efficiency by measuring the working memory needed during execution, including input data, variables, and the call stack.

Definition of space complexity

Space complexity tells you how an algorithm's memory requirements scale with input size. It's a core concept in computational complexity theory because an algorithm that's fast but devours memory may be just as impractical as a slow one.

Memory usage measurement

When you measure space complexity, you're counting the total working memory an algorithm needs while it runs. This includes three things:

• Input data stored in memory
• Temporary variables created during execution
• Call stack frames from function calls (especially in recursive algorithms)

Memory is measured in basic units (bytes or words) needed for data storage.

Asymptotic notation for space

Just like time complexity, space complexity uses Big O notation to describe the upper bound of how memory usage grows. You focus on the dominant term as input size approaches infinity and drop constants and lower-order terms. This lets you compare algorithms without worrying about specific hardware or implementation details.

For example, if an algorithm uses $3n + 5$ memory units, its space complexity is $O(n)$ because the linear term dominates as $n$ gets large.

Types of space complexity

Constant space

$O(1)$ means the algorithm uses a fixed amount of memory no matter how large the input is. Swapping two variables or scanning an array to find its maximum both use constant space because you only need a few variables regardless of input size.

Linear space

$O(n)$ means memory usage grows proportionally with input size. This happens when you create a data structure whose size depends on the input, like making a copy of an array or using a visited set in depth-first search on a graph with $n$ nodes.

Logarithmic space

$O(\log n)$ means memory usage grows logarithmically. You often see this in divide-and-conquer algorithms where each recursive call cuts the problem in half. Binary search on a sorted array, for instance, uses $O(\log n)$ stack space if implemented recursively, because the recursion depth is at most $\log_2 n$.

Quadratic space

$O(n^2)$ means memory grows with the square of the input size. This typically happens when you build a two-dimensional data structure, like a distance matrix in the Floyd-Warshall algorithm for all-pairs shortest paths, which stores a value for every pair of vertices.

Exponential space

$O(2^n)$ or more generally $O(k^n)$ means memory requirements explode as input grows. Algorithms that generate all possible subsets of a set need $2^n$ storage. This becomes impractical quickly: with just 30 elements, you'd need over a billion entries.

Analysis techniques

Recursive stack space

Every recursive call adds a frame to the call stack, consuming memory. To find the space used, you need two things:

1. Maximum recursion depth: How many calls can be stacked at once?
2. Size of each stack frame: How much data does each call store?

Multiply these together for the total stack space. A recursive function that calls itself $n$ times deep with constant-size frames uses $O(n)$ space. A function that goes $\log n$ levels deep (like binary search) uses $O(\log n)$.

Iterative space usage

Loop-based algorithms typically use less memory than recursive ones because they don't build up a call stack. You analyze them by looking at what variables are created inside the loop and whether any data structures grow with each iteration. If a loop only uses a fixed set of variables, it's $O(1)$ space regardless of how many times it iterates.

Auxiliary space vs. input space

This distinction matters more than students often realize:

• Input space: Memory used to store the input itself
• Auxiliary space: The extra memory the algorithm needs beyond the input

When someone says an algorithm is "in-place," they mean its auxiliary space is $O(1)$. The input still takes up $O(n)$ memory, but the algorithm doesn't need significant additional memory to do its work.

Space-time tradeoffs

Memory vs. speed considerations

Faster algorithms often use more memory, and vice versa. A classic example: you can compute Fibonacci numbers in $O(n)$ time using $O(n)$ space (by storing previously computed values), or in $O(1)$ space but with $O(2^n)$ time (naive recursion without memoization). The tradeoff is real, and choosing the right balance depends on your constraints.

Optimizing for space efficiency

When memory is tight, you can reduce usage through:

• In-place operations that modify data directly instead of creating copies
• Memory reuse, overwriting values you no longer need
• Streaming approaches that process data one piece at a time

These techniques matter most in resource-constrained environments like embedded systems or when processing very large datasets.

Common data structures

Arrays vs. linked lists

• Arrays store elements in contiguous memory, giving you $O(1)$ access by index. But a fixed-size array may waste space if you don't fill it, and resizing requires copying everything.
• Linked lists allocate memory per element and can grow dynamically. However, each node needs extra memory for a pointer (typically 4-8 bytes per node), which adds up.

Your choice depends on whether you need fast random access (arrays) or frequent insertions and deletions (linked lists).

Hash tables vs. trees

• Hash tables give you $O(1)$ average-case lookups and insertions, but they need extra space for the underlying array and handling collisions. A hash table is rarely more than about 70-80% full if it's performing well.
• Trees (like binary search trees) provide $O(\log n)$ operations with more predictable space usage, since each element takes roughly the same amount of memory.

Sparse matrices

A regular $n \times n$ matrix takes $O(n^2)$ space. But if most entries are zero, that's wasteful. Sparse matrix representations store only the non-zero elements, reducing space to $O(k)$ where $k$ is the number of non-zero entries. This is common in scientific computing and graph algorithms where adjacency matrices are mostly empty.

Algorithm space complexity

Sorting algorithms

Different sorts have very different space profiles:

• Merge sort needs $O(n)$ auxiliary space to merge subarrays
• Quicksort uses $O(\log n)$ space on average for its recursive call stack (though $O(n)$ in the worst case)
• Heapsort achieves $O(1)$ auxiliary space by sorting in-place

In-place sorts save memory but sometimes sacrifice stability (the property that equal elements keep their original order).

Graph algorithms

• Breadth-first search (BFS) uses $O(V)$ space for its queue, where $V$ is the number of vertices
• Depth-first search (DFS) uses $O(h)$ space for the recursion stack, where $h$ is the maximum depth of the search tree
• Dijkstra's algorithm needs $O(V)$ space for the priority queue and distance array

Dynamic programming

Dynamic programming is one of the clearest examples of a space-time tradeoff. Instead of recomputing the same subproblems over and over, you store their results:

• Memoization (top-down) stores results as you compute them, typically using $O(n)$ space
• Tabulation (bottom-up) fills in a table iteratively, using $O(n)$ or $O(n^2)$ space depending on the problem

Sometimes you can optimize further. For example, if each row of a DP table only depends on the previous row, you can keep just two rows in memory instead of the full table, reducing $O(n^2)$ space to $O(n)$.

Space complexity in practice

Memory constraints in systems

On embedded systems or mobile devices with limited RAM, space complexity directly affects whether an algorithm is usable at all. You need to consider peak memory usage during execution, not just the final result size, because a temporary spike can crash a memory-constrained system.

Big data and space limitations

When your dataset exceeds available memory, traditional algorithms break down. Solutions include:

• External memory algorithms that work with data stored on disk
• Distributed computing that spreads data across multiple machines
• Streaming algorithms that process data in a single pass with limited memory

Cloud computing considerations

Cloud platforms let you scale memory on demand, but more memory costs more money. Designing space-efficient algorithms reduces cloud computing costs, especially when processing large datasets repeatedly.

Advanced concepts

Polynomial space

Algorithms with space complexity bounded by a polynomial function of input size, like $O(n^k)$ for some constant $k$, fall into this category. This represents a broad class of practically solvable problems.

Space complexity classes

Complexity theory groups problems by the space needed to solve them:

• L (logarithmic space): Problems solvable with $O(\log n)$ extra space
• PSPACE (polynomial space): Problems solvable with polynomial space
• EXPSPACE (exponential space): Problems requiring exponential space

These classes help theorists understand the relationships between different types of computational problems.

Space-bounded computation

This area studies what you can accomplish under strict memory limits. Streaming algorithms, for instance, process data in one pass using memory much smaller than the input. This applies whenever you can't afford to load an entire dataset into memory at once.

Optimization strategies

In-place algorithms

These modify the input data structure directly, using only $O(1)$ auxiliary space. Examples include:

• In-place partitioning in quicksort
• Reversing an array by swapping elements from both ends
• In-place matrix transposition

Memory reuse techniques

Instead of allocating new memory, you overwrite or repurpose memory you're done with. Techniques include:

• Circular buffers that wrap around and reuse the same block of memory
• Pool allocation that pre-allocates a chunk and hands out pieces as needed

These are especially useful in long-running processes where repeated allocation and deallocation would fragment memory.

Compression methods

You can reduce memory usage by encoding data more compactly, though you'll spend extra computation time encoding and decoding:

• Run-length encoding replaces repeated values with a count (e.g., "AAAA" becomes "4A")
• Huffman coding assigns shorter codes to more frequent values

This trades computation time for reduced space, which is worthwhile when storage or transmission bandwidth is the bottleneck.