# Is there any general, theoretical limit to time - space tradeoff?

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: Notice, that some calculations are repeated: What one can do to speed up algorithm is to remember results of repeated calculations and reuse them. One is trading space for time.

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?