Time–Space Tradeoffs (memory for speed)

Time–space tradeoff spends more memory to buy speed—tabulation DP vs recursion, prefix sums vs recomputing, or storing extra pointers for O(1) successor jumps.

Why this shows up in the real world

Memoization in web caches trades disk for latency. Jump pointers in linked lists accelerate k-step ahead.

Core idea (explained for students)

Tabulate answers for subproblems once (O(S) space) to answer each query O(1). Alternatively compress state if memory is the bottleneck.

Try this in Python

def fib_dp_table(n: int) -> int:
    dp = [0, 1] + [0] * max(0, n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n] if n else 0


print(fib_dp_table(20))

Common mistakes

• Blowing memory with full n × m tables when rolling suffices.
• Faster asymptotic but huge constants losing on realistic n.

Key takeaways

• Plot time vs memory for a few n on your laptop to sanity-check tradeoffs.
• Document when to switch strategies (small n brute vs large n DP).