Space–time tradeoff

Biological usage of time–memory tradeoffs can be seen in the earlier stages of animal 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, look-up tables have been implemented since the very earliest operating systems.

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

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

• Baby-step giant-step algorithm for calculating discrete logarithms
• Rainbow tables in cryptography, where the adversary is trying to do better than the exponential time required for a brute-force attack. Rainbow tables use partially precomputed values in the hash space of a cryptographic 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.
• The meet-in-the-middle attack uses a space–time tradeoff to find the cryptographic 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.

• Algorithmic efficiency – Property of an algorithm
• 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 needed 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.