---
title: 'Time and Space Trade-off'
source: 'https://academia.sh/en/courses/algorithms/time-and-space-trade-off'
course: Algorithms
language: en
updated: '2026-08-17T18:07:34+00:00'
license: 'CC BY-SA 4.0'
---

# Time and Space Trade-off

Space complexity, in-place operation, the cost of the recursion stack, memoization and precomputation patterns, and the limits of the 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.

```python
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.

```python
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?

```python
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.