BIGO-4 Space cost · DSA · kartikvyas.in

Programs use memory as well as time. Space cost is counted the same way as time: how much memory the program needs, as a function of n, using the same O, Ω and Θ.

Counting memory

One number, one name, or one reference counts as one unit of memory. A list of n numbers is Θ(n). An n × n grid is Θ(n²). A dictionary with k keys is Θ(k).

Memory limits are usually less tight than time limits, but they are real. A grid of 100,000 by 100,000 numbers is 10 billion values, which will not fit in a laptop’s memory.

Input space and extra space

The input itself already takes space. Usually we count only the extra space: the memory the algorithm uses on top of its input. Compare two ways to reverse a list:

def reversed_copy(a):
    return a[::-1]            # a new list: Θ(n) extra space

def reverse_in_place(a):
    i, j = 0, len(a) - 1      # two names: Θ(1) extra space
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

An algorithm that uses only O(1) extra space is called in place. It changes its input instead of building a new one. That saves memory, but the caller loses the original order. Say clearly in your spec which one your function does.

The call stack uses space

Each function call that has not returned yet keeps a frame in memory: its arguments and local names. A recursive function that goes d calls deep keeps d frames at once. Step through the same sum written both ways:

FIG BIGO-4.1The same sum, with a loop and with recursion

Version

def total(a):
    s = 0
    for x in a:
        s += x
    return s

total(a)running

a [4, 7, 1, 6, 2]most frames at once 1

1/7

One call to total. Its only extra names are s and x.

Step 1 of 7

Both versions take Θ(n) time. The loop uses Θ(1) extra space. The recursion uses Θ(n) extra space, one frame per value. This is easy to miss, because there is no list in the code.

Recursion that halves its input, like binary search written recursively, is only log₂ n frames deep. For a million values that is about 20 frames, which is no problem.

Trading space for time

Many fast algorithms use extra memory to save time. Finding a repeated value shows the trade clearly:

Compare every pair: Θ(n²) time, Θ(1) extra space.
Sort a copy, then compare neighbours: Θ(n log n) time, Θ(n) extra space.
Keep a set of values seen so far: Θ(n) time on average, Θ(n) extra space.

Usually the set is the right choice. When memory is very tight, or the input is too big to hold twice, the other two matter. The dynamic programming stations use this trade all the time: they store answers to small problems so that they never work them out twice.

Now try BIGO-P3, Keep the first of each. A little extra space makes it fast.

BIGO-4 counts as completed once you step through the figure to the last step.

BIGO-P3Practice: Keep the first of each BIGO-5Recurrences