Time versus space

Many problems let you trade memory for speed: store a lookup table to avoid recomputing, or recompute to avoid storing. Knowing both costs lets you pick the right side for the constraints you have.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain a trade between memory and time with an example
Work out the auxiliary space of an algorithm, separate from its output
Rewrite a solution to use less memory at the cost of more time, or the reverse

In practice

A few lines that show Time versus space doing its job.

Python

def two_sum(nums, target):
    seen = {}                        # O(n) extra space...
    for i, n in enumerate(nums):
        if target - n in seen:       # ...buys O(1) lookups
            return seen[target - n], i
        seen[n] = i
    return None

# Without the dict: O(1) space but O(n^2) time.

The common mistake

Watch for

Reporting the space of the output as if it were the algorithm's working memory. Auxiliary space is what you allocate beyond the input and output, and that is what interviewers mean.

What to know first

Your roadmap puts these before Time versus space, unless you already know them.

Big-O notation

How it stays learned

Once a session shows you understand Time versus space, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Where it leads

Topics that build on Time versus space.

Lookup trade-offs

Previous in the module← Big-O notation

Next in the moduleAmortised cost →