Learning the art behind the science of algorithms. Fibonacci sequence is an integer sequence where each term after the first two terms is the sum of the preceding two terms. For a better understanding, here is how it looks: If I were to ask you this, tell me the term in this series. You would simply calculate the sum of the and the term, which in turn requires you to calculate the sum of and as well as and term respectively. If you observe carefully , we are calculating the same terms more than once. This is bad news ! We need a better algorithm to solve this problem and we will achieve that as we proceed with this article. fifth third fourth first second second third Recurrence relation for the Fibonacci sequence (Top). Naive algorithm for calculating Nth-term in a Fibonacci sequence and Time Complexity for the same. (Down) Put simply, an algorithm is a . There are two major factors which govern the efficiency of an algorithm. well defined list of steps for solving a particular problem : the data storage ( etc.)consumed in performing a given task, Space RAM, HDD : time ( or )consumed in performing a given task. Time computation time response time Space-time trade-off in a general sense state that : You can decrease the time complexity of your algorithm in exchange for greater space, or consume lesser space in exchange for slower executions. Most computers have a large amount of space, but not infinite space. Also, most people are willing to wait a little while for a big calculation, but not forever. So if your problem is taking a long time but not much memory, a space-time trade-off would let you use more memory and solve the problem more quickly. Or, if it could be solved very quickly but requires more memory than you have, you can try to spend more time solving the problem in the limited memory. The most common condition is an algorithm using a . 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 let you 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. lookup table A space-time tradeoff can be used with the 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 decreases the amount of space it takes, but it takes time to run the compression algorithm Larger code size can be used to increase program speed when using . This technique makes the 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. loop unwinding In the field of , using space-time trade-off, the attacker is decreasing the exponential time required for a . 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 attack uses a space-time trade-off to find the cryptographic key in only 2^{n+1} encryptions (and O(2^{n}) space) compared to the expected 2^{2n} encryptions (but only O(1) space) of the normal attack. cryptography brute-force attack Rainbow tables Dynamic programming is another example where the time of solving problems can be decreased by using more memory. The above Fibonacci problem can be solved faster with DP. This will take O(n) time and space (which is a much better improvement in time, but now we need to store the results of the previous executions instead of just requiring them on demand). Keep in mind that this is just one example, there are tons of cases that explores this space-time trade-off (and the choice might not be as ‘clear-cut’ as this). If you have made it till here, here’s a good news for you. Something extra from the bag: Space-time trade-offs are also prevalent in Biology. How you ask? Using stored knowledge or encoding stimuli reactions as “instincts” in the DNA avoids the need for “calculation” in time-critical situations. Thank you for your time. If you like my writing, you can find more of my content on . If you have 12 seconds, I’d love to read your comment below.. 👏 ⬇⬇ Quora Do these concepts make sense to you? If this post was helpful, please click the clap button below a few times to show your support!

Too Long; Didn't Read

Making security fun one episode at a time

Getting the best of both worlds : Space-time trade-offs in algorithms.

Too Long; Didn't Read

Amogh Singhal

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Getting the best of both worlds : Space-time trade-offs in algorithms.

Too Long; Didn't Read

Amogh Singhal

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES