08:13 am, 10 Apr 06

### time-space tradeoffs

I have a friend who, whenever presented a new algorithm, approach, or system, always asks the question: What is the time-space tradeoff? He's a little obsessed, and it's a little amusing, but it's also true that almost every data structure / algorithm can be considered in terms of that. (Sorting can be is O(n) if you have unique data and enough memory...)

All of that is mostly lead-up to say that rainbow tables are a great hack, and a perfect example of a good time-space tradeoff.

All of that is mostly lead-up to say that rainbow tables are a great hack, and a perfect example of a good time-space tradeoff.

mr_um2312evanmr_um2312Maybe it is a silly question, but are there rules or equations governing how one can trade computation time for memory space?

It feels like it is an important question, but when dealt with in terms of algorithms (as far as I have seen) it always feels like an engineering issue rather than a science question.

evanMuch of the time (see sorting algorithms, for example) it's actually that different algorithms, with very different approaches to solving the same problem, use more or less time and space. Other times (like the article I link to above) the tradeoff is explicit: "...about 2 seconds with a table set of 1.1G bytes. It takes about 16 seconds with a table set of 388M bytes..." It's hard to extrapolate from two data points (and there are likely lots of things involved here like disk speeds), but you could derive a formula relating disk space to speed (e.g., the disk space is a factor of 3 while the time is a factor of 2**3, so maybe there's something logarthmic).

Bloom filters have an explicit formula for the space/accuracy (which relates to time) tradeoff.

dan_eratMaking a good reduction (hash-to-password) function seems hard. You'd end up with a lot of duplication between chains, I'd think.

evanriximedge_walkerI like this way of expressing it:

—Terje Mathisen