Skip to content

Time-Space Trade-off Principle

Computation can be exchanged for memory and vice versa; precomputing and storing results trades space for time, while recomputing on demand trades time for space.

Tension Addressed

Time vs. Space (directly embodies this tension)

Recognizable As

Caching strategies, lookup tables, memoization, compression algorithms (space vs. decode time), indexes in databases, precomputed results

Canonical Sources

Cobham, The Intrinsic Computational Difficulty of Functions (1965); Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities (1970)

Transfers To

Database indexing, web caching, compiler optimization (register allocation), embedded systems design, mobile app architecture

Sub-concepts: - Caching as universal pattern: Store computed results to avoid recomputation - Lazy vs. eager evaluation: Defer computation until needed vs. precompute speculatively