Time and Space Trade-off

So far, only a single resource has been counted: operation count. Yet algorithms also consume memory, and the two resources frequently substitute for one another. Doing fewer operations by using more memory, or the reverse, is possible for most problems.

This lesson defines the second axis and shows the patterns of the trade-off between them.

Space Complexity

Space complexity is the rate at which the amount of memory used grows as a function of input size. The same notations used for time complexity apply.

There are two separate quantities, and confusing them is a common error:

Total space is all memory used, including the input. Every algorithm operating on an $n$-element array uses at least $O(n)$ total space.

Auxiliary space is memory allocated beyond the input. This is what is meaningful in comparisons, because holding the input is already mandatory.

Algorithms whose auxiliary space is constant are called in-place. The following function that reverses an array is in-place: no matter how many elements there are, it uses no more than three variables.

def reverse_in_place(array: list[int]) -> None:
    """Reverses the array in place. Auxiliary space: O(1)."""
    left, right = 0, len(array) - 1
    while left < right:
        array[left], array[right] = array[right], array[left]
        left += 1
        right -= 1


def reverse_copy(array: list[int]) -> list[int]:
    """Produces a new array. Auxiliary space: O(n)."""
    return [array[i] for i in range(len(array) - 1, -1, -1)]


a = [1, 2, 3, 4, 5]
reverse_in_place(a)
print(a)                                    # [5, 4, 3, 2, 1]
print(reverse_copy([1, 2, 3, 4, 5]))        # [5, 4, 3, 2, 1]

Both are $O(n)$ in time; the axis where they differ is space. The choice depends on whether the caller needs the original array and how constrained memory is.

The Recursion Stack Consumes Space

In a recursive solution, memory is used even if no array is explicitly allocated: every pending call holds a frame on the call stack introduced in the Programming Fundamentals course.

The space cost is the number of calls at the deepest point — not the total number of calls.

Structure	Maximum depth	Auxiliary space
Linear recursion ($n$ steps)	$n$	$O(n)$
Halving recursion	$\log n$	$O(\log n)$
Tail recursion (if converted to a loop)	$1$	$O(1)$

The distinction has a practical consequence: on a million-element array, a linearly deep recursion exceeds the runtime’s stack limit. The loop-based version of the same algorithm does not hit the limit.

Classic Trade-off Patterns

There are several established ways to convert memory into time.

Memoization. Computed results are stored and not recomputed when requested again. Time decreases, space increases.

Precomputation. Results are written into a table before a query arrives. Query cost drops to constant, and table space is paid for.

Indexing. The hash table and trees from the Data Structures course lower search cost in exchange for extra structure.

Compression. The reverse direction: space decreases, and encoding-decoding work increases time.

The effect of memoization is seen most clearly in a recursion that does the same computation twice.

def fib_naive(n: int, counter: list[int]) -> int:
    counter[0] += 1
    if n < 2:
        return n
    return fib_naive(n - 1, counter) + fib_naive(n - 2, counter)


def fib_tabulated(n: int, counter: list[int], table: dict[int, int]) -> int:
    counter[0] += 1
    if n < 2:
        return n
    if n not in table:
        table[n] = fib_tabulated(n - 1, counter, table) + fib_tabulated(n - 2, counter, table)
    return table[n]


for n in (10, 20, 30):
    a, b = [0], [0]
    print(n, fib_naive(n, a), a[0], fib_tabulated(n, b, {}), b[0])

# 10 55 177 55 19
# 20 6765 21891 6765 39
# 30 832040 2692537 832040 59

Call count drops from exponential to linear: for thirty, fifty-nine calls instead of two and a half million. The price paid is a dictionary of $n$ entries — that is, $O(n)$ auxiliary space.

Same Problem, Two Balance Points

The trade-off becomes concrete by writing two solutions to a single problem. The problem: does an array contain two elements whose sum equals a given target?

def two_sum_hash(array: list[int], target: int) -> tuple[int, int] | None:
    """Time O(n), auxiliary space O(n)."""
    seen: dict[int, int] = {}
    for i, value in enumerate(array):
        if target - value in seen:
            return seen[target - value], i
        seen[value] = i
    return None


def two_sum_two_pointer(array: list[int], target: int) -> tuple[int, int] | None:
    """On a sorted array, time O(n), auxiliary space O(1)."""
    left, right = 0, len(array) - 1
    while left < right:
        total = array[left] + array[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None


print(two_sum_hash([8, 3, 11, 5, 2], 13))          # (0, 3)  — 8 + 5
print(two_sum_two_pointer([2, 3, 5, 8, 11], 13))   # (0, 4)
print(two_sum_hash([8, 3, 11, 5, 2], 100))         # None

The first solution works in a single pass on an unsorted array, but keeps a dictionary of $n$ entries. The second uses no auxiliary space at all, but in exchange requires the array to be sorted; if the sorting cost is added, the total becomes $O(n \log n)$.

The choice is not the answer to “which is better”; it depends on which resource is constrained. If memory is plentiful and only a single query will be made, the first; if memory is tight or the array is already sorted, the second.

The Trade-off Does Not Always Hold

Two caveats prevent treating the trade-off as a mechanical rule.

Less space is sometimes faster. Because of the memory hierarchy from the How Computers Work course, a small, contiguous structure fits in cache and can run faster than a large, scattered one. Here, reducing space reduces time as well.

Some improvements gain on both axes. An idea that reduces a quadratic algorithm to linearithmic usually does not demand extra space either. The trade-off holds when the algorithm is held fixed — not when a better algorithm is found.

For this reason, the order is to look first at improving the algorithm itself, and to resort to the trade-off only afterward.

Decision Criterion

In practice, the choice is made with three questions:

1. Which resource is constrained? Memory in an embedded system, time in batch processing.
2. How many times will the result be used? Precomputation is a loss for a one-off calculation; it pays for itself with many queries.
3. How large will the input grow? If space grows linearly, past a certain point the input no longer fits in memory and the solution becomes invalid.

The third question is often skipped: a time overrun is a delay, but a memory overrun is the work stopping entirely.

Summary

• Space complexity is the rate at which memory usage grows relative to input; total space and auxiliary space are separate quantities.
• Algorithms whose auxiliary space is constant are called in-place.
• Recursion consumes as much stack space as the call count at the deepest point.
• Memoization, precomputation, and indexing convert memory into time; compression works in the reverse direction.
• Solutions to the same problem at different balance points are chosen according to which resource is constrained.
• The trade-off holds while the algorithm is fixed; a better algorithm can gain on both axes.

Next Step

The tools of analysis are complete: cost has been defined, expressed with notation, computed, and split into two axes. The next topic will apply these tools for the first time to a serious family of algorithms — searching and sorting. Half a dozen solutions to the same problem will be compared with exactly these metrics.