Measuring Memory Use

Memory grows too

Space complexity measures how much memory an algorithm needs as a function of n. Usually we count auxiliary space: memory used in addition to the input, such as extra arrays, hash tables and the recursion stack. An algorithm that uses only a few variables regardless of n is O(1) auxiliary space and is called in-place: reversing an array by swapping ends, or insertion sort. Building a set of seen elements is O(n) space; creating an n × n distance matrix is O(n²) space. Some texts include the input itself (total space), so state which you mean. Space matters because memory is limited, allocation and garbage collection take time, and data that does not fit in CPU caches or RAM is dramatically slower to process. In interviews, always state both time and space: "O(n) time and O(1) extra space" is a stronger answer than one that ignores memory.

Input space and auxiliary space

The input is given; auxiliary space is what the algorithm adds on top.

Same task, different space

Reversing a list in place versus creating a reversed copy.

def reverse_in_place(a):
    i, j = 0, len(a) - 1
    while i < j:                 # O(n) time
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    # O(1) auxiliary space: just two indices

def reversed_copy(a):
    return a[::-1]               # O(n) time, O(n) auxiliary space for the new list

def pairwise_distances(points):
    n = len(points)
    return [[dist(p, q) for q in points] for p in points]   # O(n^2) time and space

Output space is usually not auxiliary

If a function must return n results, storing them is unavoidable. Many texts exclude required output from auxiliary space; say explicitly whether you are counting it.

Quick check: What is the auxiliary space of reversing an array in place by swapping elements from both ends?

• O(1)
• O(n)
• O(log n)
• O(n²)