The time-space tradeoff is one of the most useful mental models in all of algorithm design: very often, you can make an algorithm run faster by using more memory, or shrink its memory footprint by letting it run slower. There's rarely a free lunch where both improve at once — understanding this tradeoff, and consciously deciding which resource you can afford to spend, is a core part of designing good algorithms.

Neither direction is automatically "better." The right choice depends entirely on what's actually constrained in your situation — a mobile app running on limited RAM has very different priorities than a backend service with plenty of memory but strict latency requirements.

Example: Memoization Trades Memory for Speed

This is the clearest example in the entire course. Naive recursive Fibonacci uses almost no extra memory (just the call stack), but runs in O(2^n) time because it recomputes the same values endlessly. Add a memoization cache — spending O(n) extra memory — and the time complexity drops all the way to O(n).

# O(2^n) time, O(n) space (just the call stack) — slow, minimal memory
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# O(n) time, O(n) space (recursion + cache) — fast, more memory
def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n <= 1:
        return n
    if n not in cache:
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

That extra dictionary is the entire tradeoff: a little more memory in exchange for an exponential-to-linear speedup. See the full comparison, including the bottom-up version, in our dynamic programming guide.

Example: Hash Tables vs Smaller Structures

A hash table gives average O(1) lookup, but it needs extra memory overhead for its internal bucket array (sized larger than the actual number of entries to keep collisions manageable) — typically more memory than a plain sorted array holding the same data. A sorted array uses tighter, more compact memory but only offers O(log n) lookup via binary search. If lookup speed matters more than memory footprint, the hash table wins; if you're memory-constrained and can tolerate logarithmic lookups, the sorted array wins.

Example: Precomputing vs Computing on the Fly

If a value — say, the first million prime numbers, or a lookup table of factorial values — will be requested repeatedly, it's often worth computing it once and storing it (spending memory) rather than recalculating it from scratch on every request (spending time). This is the same idea behind caching in web applications: a cache trades memory for avoiding repeated expensive work, whether that work is a calculation or a database query.

How to Decide Which Resource to Spend

Ask which constraint actually bites in your situation. Running on a memory-constrained device (embedded systems, mobile) or processing enormous datasets that barely fit in memory at all? Lean toward the lower-memory option even if it's slower. Serving latency-sensitive requests where users are waiting, and memory is comparatively cheap? Lean toward the faster, higher-memory option. There's no universally correct answer — which is exactly why this tradeoff is worth naming and reasoning about explicitly, rather than reaching for whichever approach happens to come to mind first.