1
$\begingroup$

In many algorithms, one can spot that improvements in time often are occupied by more memory requirements. For example usage of cache allows to speed up calculations by saving results in memory.

Is there any theoretical limit of "time-space tradeoff" similar to Amdahl's law limiting speed-up from the parallelization of calculations?

Example

Assumption: we will neglect the size of the call stack.
To illustrate how time-space tradeoff works let us think about Fibonacci sequence calculations.
One can calculate Nth Fibonacci seq. element using the below equation:

fib(n) = fib(n-1) + fib(n-2)
fib(1) = fib(2) = 1 

Notice, that to compute Nth element we need to calculate 2 previous ones. To calculate each of these we need to calculate 2 previous ones for each of them and so on...

Straightforward implementation be:

function fib(n) {
  if (n == 1 || n == 2)
    return 1;
  return fib(n-1) + fib(n-2);
}

Let's visualize this using graph for N=6: enter image description here Notice, that some calculations are repeated: Repeated elements What one can do to speed up algorithm is to remember results of repeated calculations and reuse them. One is trading space for time.

Implementation of such tradeoff:

const resultsCache = [1,1];
function fib(n) {
  if (resultsCache[n])
    return resultsCache[n];
  fibN = fib(n-1) + fib(n-2);
  resultsCache[n] = fibN;
  return fibN;
}

Question

Is there any theoretical limit of "time - space tradeoff" as presented in above example? It is how much we can speed up algorithm by using more space?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.