Space/Time Tradeoffs

Most optimisation is trading one resource for another. Naming the trade explicitly is a senior signal, because it shows you know what you spent.

Precomputation — a prefix sum array costs O(n) space and turns every range-sum query from O(n) into O(1). Worth it when queries are frequent, wasteful for a single query.

Memoisation — cache subproblem results to avoid recomputation. Turns exponential recursion into polynomial, and the cache is the cost. It is the same trade a web cache makes, one abstraction level down.

Hashing for lookup — building a set of seen values costs O(n) memory and converts an O(n²) nested scan into O(n). This is the single most common optimisation in interviews, and it is worth saying "I'll trade O(n) space for O(n) time" as you do it.

When memory is the constraint the trade reverses. Sorting in place at O(n log n) beats hashing when you cannot afford the extra array. Streaming algorithms give approximate answers in bounded memory — HyperLogLog estimates distinct counts in kilobytes rather than storing every value, and a Bloom filter answers "definitely not present" or "probably present" in a fraction of the space of a real set.

Measure before you trade. Each resource is only worth spending where it is genuinely scarce, and intuition about which one is scarce here is unreliable — a cache that introduces an invalidation bug to save two milliseconds is a bad trade made confidently. Profile first, and prefer the version of the trade that is easy to undo when the measurement changes.

There is a third resource, and it is often the largest. Every precomputed copy is complexity somebody maintains: a cache is a consistency obligation, a denormalised column is an update path, a memo table is a lifetime question nobody asked. None of that appears in a comparison of two Big-O expressions, and it is usually what decides whether the optimisation survives the next six months. The simplest version that is fast enough beats the fastest version nobody dares change.

The real-world version is the same reasoning: a denormalised table, a materialised view, and a cache are all precomputation. The cost is memory plus a consistency obligation. Recognising that a database index is a space-for-time trade is the point where these two tracks meet.