This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) This article mayrequirecleanup to meet Wikipedia'squality standards. The specific problem is:casual tone, lack of detail. Please helpimprove this article if you can.(March 2014) (Learn how and when to remove this message) This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Space–time tradeoff" – news ·newspapers ·books ·scholar ·JSTOR(February 2025) (Learn how and when to remove this message) (Learn how and when to remove this message)

Aspace–time trade-off, also known astime–memory trade-off orthe algorithmic space-time continuum incomputer science is a case where analgorithm orprogramtrades increased space usage with decreased time. Here,space refers to thedata storage consumed in performing a given task (RAM,HDD, etc.), andtime refers to the time consumed in performing a given task (computation time orresponse time).

The utility of a given space–time tradeoff is affected by relatedfixed andvariable costs (of, e.g.,CPU speed, storage space), and is subject todiminishing returns.

Biological usage of time–memory tradeoffs can be seen in the earlier stages ofanimal behavior. Using stored knowledge or encoding stimuli reactions as "instincts" in the DNA avoids the need for "calculation" in time-critical situations. More specific to computers,lookup tables have been implemented since the very earliest operating systems.^{[citation needed]}

In 1980Martin Hellman first proposed using a time–memory tradeoff forcryptanalysis.^[1]

A common situation is an algorithm involving alookup 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.

Database Management Systems offer the capability to createdatabase index data structures. Indexes improve the speed of lookup operations at the cost of additional space. Without indexes, time-consumingfull table scan operations are sometimes required to locate desired data.

A space–time trade off can be applied to the problem of data storage. If data is stored uncompressed, it takes more space but access takes 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 thedecompression algorithm). Depending on the particular instance of the problem, either way is practical. There are also rare instances where it is possible to directly work with compressed data, such as in the case of compressedbitmap indices, where it is faster to work with compression than without compression.

Storing only theSVG source of avector image and rendering it as abitmap image every time the page is requested would be trading time for space; more time used, but less space. Rendering the image when the page is changed and storing the rendered images would be trading space for time; more space used, but less time. This technique is more generally known ascaching.

Larger code size can be traded for higher program speed when applyingloop unrolling. This technique makes the code longer for each iteration of a loop, but saves the computation time required for jumping back to the beginning of the loop at the end of each iteration.

Algorithms that also make use of space–time tradeoffs include:

• Baby-step giant-step algorithm for calculatingdiscrete logarithms
• Rainbow tables in cryptography, where the adversary is trying to do better than the exponential time required for abrute-force attack. Rainbow tables use partially precomputed values in the hash space of acryptographic hash function to crack passwords in minutes instead of weeks. Decreasing the size of the rainbow table increases the time required to iterate over the hash space.
• Themeet-in-the-middle attack uses a space–time tradeoff to find thecryptographic key in only${\displaystyle 2^{n+1}}$ encryptions (and${\displaystyle O(2^n)}$ space) versus the expected${\displaystyle 2^{2n}}$ encryptions (but only${\displaystyle O(1)}$ space) of the naive attack.
• Dynamic programming, where the time complexity of a problem can be reduced significantly by using more memory.
• Time/memory/data tradeoff attack which uses the space–time tradeoff with the additional parameter of data.

• Algorithmic efficiency
• Blum's speedup theorem – Rules out assigning to arbitrary functions their computational complexity
• Computational complexity – Amount of resources to perform an algorithm
• Computational resource – Something a computer needs to solve a problem, such as processing steps or memory
• Savitch's theorem – Relation between deterministic and nondeterministic space complexity

• Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.
• Once Upon a Time-Memory Tradeoff.

• Software optimization

• Articles with short description
• Short description is different from Wikidata
• Articles needing cleanup from March 2014
• All pages needing cleanup
• Cleanup tagged articles with a reason field from March 2014
• Wikipedia pages needing cleanup from March 2014
• Articles needing additional references from February 2025
• All articles needing additional references
• Articles with multiple maintenance issues
• All articles with unsourced statements
• Articles with unsourced statements from June 2013