What is Space-time tradeoff?
In [[computer science]], a '''space-time''' or '''time-memory tradeoff''' is a way of solving a problem or calculation in less time by using more storage space (or [[memory]]), or by solving a problem in very little space by spending a long time. Most computers have a large amount of space, but not [[Infinity|infinite]] space. Most people are willing to wait a little while for a big calculation, but not forever. So if a problem is taking a long time but not much memory, a space-time tradeoff would use more memory and solve the problem more quickly. The most common condition is an [[algorithm]] using a [[lookup table]]. This means that the answers for some question for every possible value can be written down. One way of solving this problem is to write down the entire lookup table, which will find answers very quickly, but will use a lot of space. Another way is to calculate the answers without writing down anything, which uses very little space, but might take a long time. A space-time tradeoff can be used with the problem of [[Data storage device|data storage]]. If data is stored uncompressed, it takes more space but less time than if the data were stored [[Data compression|compressed]] (since compressing the data decreases the amount of space it takes, but it takes time to run the [[Data compression|compression]] [[algorithm]]). Larger code size can be used to increase program speed when using [[:en:Loop_unrolling|loop unwinding]]. This [[technique]] makes the [[Computer program|program code]] longer for each iteration of a loop, but saves the computation time needed for jumping back to the beginning of the loop at the end of each iteration. In the field of [[cryptography]], using space-time tradeoff, the attacker is decreasing the [[Exponential function|exponential]] time required for a [[brute force attack]]. [[:en:Rainbow_table|Rainbow tables]] use partially precomputed values in the hash space of a [[cryptographic hash function]] to [[Cryptanalysis|crack]] [[password]]s in minutes instead of weeks.