Explain 'Space-Time' tradeoff.

Explain 'Space-Time' tradeoff.

Approach: Frame it as a rate rather than a slogan: what a unit of memory buys in time, and at what size the exchange stops paying.

The space-time tradeoff is the exchange of memory for execution time, and the useful form of it is a rate: a lookup table of size m turns a computation of cost c into one memory access, so the saving is c minus the cost of a cache miss, which is worth it only while the table stays resident. A rainbow table trades storage against the cost of recomputing hashes. Memoization turns exponential recursion into polynomial time at the cost of storing every subproblem. Compression runs the exchange in reverse, spending processor cycles to shrink a working set so that it fits in cache, which is why a compressed column often reads faster than an uncompressed one despite the extra work. The tradeoff stops being monotone once the table exceeds the cache, because the memory access is then itself a cache miss and the precomputation buys nothing.

Follow-up: At what table size does precomputation stop paying on a machine with a 32 MB last level cache?

Key concepts: memoization, lookup table, cache residency, compression, precomputation.