Space-time tradeoff

From Wikipedia, the free encyclopedia

In computer science, a space-time or time-memory tradeoff is a situation where the memory use can be reduced at the cost of slower program execution, or vice versa, the computation time can be reduced at the cost of increased memory use. As the relative costs of CPU cycles, RAM space, and hard drive space change — hard drive space has for some time been getting cheaper at a much faster rate than other components of computers^{[citation needed]} — the appropriate choices for space-time tradeoffs have changed radically. Often, by exploiting a time-memory tradeoff, the complexity class of a problem can be changed altogether.

The most common situation is an algorithm involving a lookup table: an implementation can include the entire table, which reduces computing time, but increases the amount of memory needed, or it can compute table entries as needed, increasing computing time, but reducing memory requirements.

A space-time tradeoff can be applied to the simple problem of data storage. If data is stored uncompressed, it takes more space but less time than if the data were stored compressed (since compressing the data reduces the amount of space it takes, but it takes time to run the compression algorithm). Depending on the particular instance of the problem, either way is practical.

Another example is displaying math on Wikipedia. Storing only the LaTeX source and rendering it as an image every time the page was requested would be trading time for memory - more time used, but less memory. Rendering the image when the page was saved and storing the rendered images would be trading memory for time - more memory used, but less time.

Algorithms that make use of space-time tradeoffs to achieve better running times include the baby-step giant-step algorithm for calculating discrete logarithms.

In other areas, space-time tradeoffs can be made when performing brute force attacks against cryptosystems through the creation of rainbow tables. The meet-in-the-middle attack is an application of space-time tradeoffs.