Algorithms & Complexity

Time Complexity vs Space Complexity

Speed and memory are not free, and optimizing one often costs the other. Understanding the trade-off lets you make deliberate choices rather than guessing.

Published May 3, 2026

Time complexity describes how the number of operations in an algorithm grows with input size. Space complexity describes how much memory it uses. Both are expressed in Big-O notation, and both matter — but they matter differently depending on what you're building.

Space complexity: what counts

Space complexity includes the memory used by the algorithm itself (auxiliary space) plus the space taken up by the input. In most practical analysis, when people say "space complexity" they mean auxiliary space — the extra memory beyond what storing the input requires.

An algorithm that makes a copy of its input to avoid modifying it uses O(n) auxiliary space. An algorithm that sorts in-place and uses only a handful of variables uses O(1) auxiliary space, regardless of input size.

# O(n) space: creates a new list proportional to input
def doubled(items):
    return [x * 2 for x in items]   # allocates new list of size n

# O(1) space: modifies in-place, constant extra memory
def double_in_place(items):
    for i in range(len(items)):
        items[i] *= 2

The classic trade-off: memoization

Memoization trades space for time: you store the result of expensive computations so you don't repeat them. The Fibonacci example from the recursion article is a perfect illustration:

# Naive recursive Fibonacci: O(2^n) time, O(n) space (call stack)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Memoized Fibonacci: O(n) time, O(n) space (the cache)
cache = {}
def fib_memo(n):
    if n in cache: return cache[n]
    if n <= 1: return n
    cache[n] = fib_memo(n-1) + fib_memo(n-2)
    return cache[n]

The memoized version is dramatically faster (exponential time reduced to linear) but uses O(n) space for the cache. The trade-off is almost always worth it here because exponential time makes the problem intractable at even modest input sizes.

Hash tables: the ubiquitous time-for-space trade

Hash tables (dicts, maps, sets) are the most common time-for-space trade in everyday programming. Looking up a value in an unsorted list is O(n). Looking it up in a hash set is O(1) average. The cost: the set uses O(n) memory.

# O(n^2) time, O(1) extra space
def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# O(n) time, O(n) extra space
def has_duplicate_fast(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Sorting algorithms: the comparison

Different sorting algorithms make different time/space choices:

Merge sort: O(n log n) time, O(n) space. Stable (preserves equal elements' order), guaranteed O(n log n) worst-case. Costs extra memory for the merge step.
Quicksort: O(n log n) average time, O(log n) average space (call stack). O(n²) worst-case, O(n) worst-case space. Faster in practice than merge sort on most inputs, but not stable.
Heap sort: O(n log n) time, O(1) space. In-place, no extra memory. Slower than quicksort in practice due to cache behaviour, but space-optimal.

When space matters more than time

Memory is the binding constraint in several real scenarios:

Embedded systems and microcontrollers: might have kilobytes of RAM. An O(n) space algorithm may be literally impossible.
Processing data larger than RAM: when your dataset doesn't fit in memory, you need streaming or external-sort approaches, which sacrifice time to reduce memory footprint.
Cache efficiency: even when RAM is plentiful, algorithms with large working sets suffer from cache misses. An O(n) extra space algorithm may be slower in wall-clock time than its O(1) space alternative because of memory access patterns.

When time matters more than space

For most server-side application code, memory is cheap and abundant. A few megabytes of cache that eliminates millions of database queries is a clear win. The thumb rule: prefer the faster algorithm unless you have a demonstrated memory constraint or you're working in a memory-limited environment.

Measuring instead of guessing

Theory tells you the shape of growth; measurement tells you actual costs. Profile both before optimizing. Sometimes the "slower" algorithm wins in practice because it has better cache behaviour, a smaller constant factor, or a better fit for the actual input distribution. Big-O analysis is the starting point, not the ending point.