# An underestimated tradeoff between Memory and the Effectivity of Computation?

Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form such as runtime?

(A good purely theoretical startig point to work with could really be a number sequence...)

• What do you expect from answer if answer is "no"? What model of computation do you have in mind? – Evil Oct 7 at 20:22
• I thought of Turing machines, but really any model with the possibility of calculation could be used – SomeGuy Oct 8 at 5:28

I'm not sure I understand your question entirely, but I'm going to assume that you're talking about the space-time tradeoff. The gist of the aforementioned tradeoff is as you put it, in the context of an algorithm, the balance you have to strike between the memory it will use (its space complexity) and the time it will take to run (its time complexity). Obviously, the faster you want it to run, the more memory you will need to use, and vice-versa. The tradeoff is in general present in most fields of computer science besides pure algorithm design, but this provides I believe a nice abstract starting point.

Let's start with the bad news: from a rigid theoretical computer science point of view, tough luck, no such unifying formula exists and it is actually a fairly well-known open problem (for more info you may want to check this question about the space-time tradeoff, but it is fairly technical). Even worse, few general results are known about this.

Now the good news, of which there are two. First of all, I highly encourage you to think about the problem yourself and come up with your own (even incomplete theory), as it isn't very hard to qualitatively come up with some pretty interesting remarks.

For instance, let us try to develop a (very!) basic theory here. At its core, a result to be obtained through computation can be decomposed into a bunch of dependencies and operations. For instance, to compute c=a+b, you need to know a and b (the dependencies, also known as operands), and add them together (the operation). This decomposition can be applied iteratively many times until all of the dependencies are directly known (present in the problem instance/the input you receive). There are many ways of looking at this, one of them is as a DFG (Data Flow Graph), but there are of course many more with varying degrees of complexity, which each offer accuracy for different factors. For convenience, have this nice picture of a DFG:

Abstracting the compute cost of one operation to 1 (no matter its complexity or the number of operands), we can see that the lower time bound to obtain the value of a node of the DFG is equal to the length of the longest path from the node to an input operand. Indeed, if we assume entirely parallel computation (possible if no interdependencies exist between nodes at the same depth), this bound can be attained. If we would however assume entirely serial computation, we would need to add the cost of obtaining each result one by one and I choose not complicate myself with this here. If we add memoization, this time becomes the length of the longest path from the node to a memoized operand (but we stop when we reach the first one on a given path backwards from the target node).

This sounds suspiciously simple, right? If we know the DFG beforehand and we assume parallelism, it indeed isn't very complicated, but a few avenues of thought would be if we consider as mentioned serial (or partly serial execution) and then memoization strategy.

I'll just point out that while it's not what you're looking for, for practical purposes it's always a good idea to benchmark on real hardware as well.

Now since I mentioned that there are two good news: there are bounds on this tradeoff which have been found and proven for specific problems and computation models. If you're interested, you can find some of these purely theoretical results in this answer.

• I tried to answer your post below. Cheers ✌ – SomeGuy Oct 9 at 13:48

• Wel, let's say we indeed define a cost function for computing $c$ and one for memoizing $m$. Both of these take as input a target $t$ and output the cost of respectively computing and memoizing it $c$ (in arbitrary units if we want to stay in the real world and not just mathematical abstraction). The gains for an isolated target $t$ then would be: $c(t) - m(t)$. This can generalize to multiple interdependent targets, and it then becomes a problem of maximizing the total gain by choosing what to memoize and what to compute. – David Cian Oct 9 at 21:41