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

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:

The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling; this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13 and 21.

If I were to ask you this, tell me the fifth term in this series. You would simply calculate the sum of the third and the fourth term, which in turn requires you to calculate the sum of first and second as well as second and third 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.

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 well defined list of steps for solving a particular problem. There are two major factors which govern the efficiency of an algorithm.

  1. Space : the data storage (RAM, HDD etc.)consumed in performing a given task,
  2. Time : time (computation time or response time)consumed in performing a given task.

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 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 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.

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 loop unwinding. 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.

read original article here