TRT
Sign in
mediumFoundationsconcept

When would you trade memory for speed, and when not?

Discuss time–space trade-offs with concrete examples, the hidden memory costs of common code, and when the slower, smaller solution is the right one.

TRT practice prompt — not a verified question from a named employer.

The Runtime Theory Team1 min read
Learn it firstSpace and hidden costsTime is only one bill an algorithm pays. Memory is the other, and both hide in copies, allocations, recursion and constant factors that Big-O leaves out.

A strong answer

Many problems get faster when you spend memory: a hash set turns an O(n²) duplicate check into O(n), a cache avoids recomputing results, an index avoids scanning a table, and dynamic programming stores subproblem answers. Usually that trade is worth making, because memory is cheaper than time, and quadratic time stops scaling long before memory runs out.

I would not make it when:

  • The data is huge and the helper structure is as big as the input: a hash set of a billion keys may not fit, while sorting in place and scanning neighbors will.
  • Memory is multiplied by concurrency. O(n) extra per request, times a thousand concurrent requests, can exhaust a server that handles each one comfortably.
  • The memory isn't free in time either. Big allocations cost allocation and garbage-collection time, and a structure that doesn't fit in cache can be slower than recomputing.
  • It is stack memory. Deep recursion uses O(depth) stack space and can overflow; an explicit stack or an iterative version avoids that.

I also look for memory that is spent by accident: copies from slicing or sorting, strings built by repeated concatenation, and helper collections that live longer than they need to. And I state both costs in my answer, for example "O(n) time and O(n) space, or O(n log n) time and O(1) extra space if memory is tight".

What the interviewer is listening for

  • Concrete examples of the trade in both directions.
  • Awareness of concurrency, stack depth and allocation as real costs.
  • Stating time and space together.

Common mistakes

  • Ignoring space entirely.
  • Counting the input as extra space, or forgetting the recursion stack.
  • Assuming the faster algorithm is always better, even when it can't fit in memory.

This answer walks

Practice follow-ups

  1. 01How much memory does a recursive DFS on a graph of a million nodes in a long chain need?
  2. 02Your service handles 1,000 concurrent requests and each builds an O(n) helper set. What changes?
  3. 03Find a duplicate in an array of n + 1 numbers from 1 to n without modifying it, in O(1) space.
  4. 04When would you choose to recompute a value instead of caching it?

More interviews in this track

hard · dsaHow would you count distinct users across a fleet of services in constant memory?hard · dsaWhy can't a sparse table answer range sums?hard · dsaWhy is a lock-free stack still hard to get right?

Not started

Sign in to save your learning progress.

Sign in to save