Space-time tradeoff

In computer science, a space-time or time-memory trade-off is a situation where the programmer can reduce computer storage use at the cost of slower program execution, or can reduce computation time at the cost of increased memory use. 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.

For another example, bubble sort is a sort algorithm that uses Big O notation(1) (constant) memory space and O( n 2) (quadratic) time. In other words, its memory requirement is unrelated to the length of the list to be sorted, but its time requirement grows proportionally to the square of the length of the list. In the case of the sorting problem, a space-time tradeoff can be made by using a different algorithm such as binary tree sort. Its memory requirement is O( n ) (linear), but its time requirement is O( n lg n ) ( linearithmic ) which is optimal for a general sort algorithm. Binary tree sort s time requirement grows more slowly than bubble sort s, but its memory requirement grows faster.

In the case of the sorting problem, all-around better algorithms exist, such as heapsort, which combines the good qualities of bubble sort and binary tree sort: its time requirement is O( n lg n ), and its memory requirement is O(1).

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