Let's say that my CPU can be made arbitrarily faster (or I can become arbitrarily patient waiting for the CPU to complete its task), and let's say that my memory (e.g. RAM) can be made arbitrarily larger. I.e. none have any limits/caps.

My question is, what is the tightest law, or theorem, that maps change in space/ram into change in time/cpu?

E.g. I'm looking for something like: regardless of the hardware used, for a given algorithm $a$, if we (say) double the RAM, the CPU time will shrink in half.

Of course the above is just an example, and not meant to be exactly like it. I am simply looking for the latest theories in this area that give the tightest bounds on mapping space-memory relationship.

  • $\begingroup$ The first paragraph is like: compute all of the table and store, sort, and use. The Time-Memory trade-off is computed according to your budget and your patience. $\endgroup$ – kelalaka Nov 7 '20 at 18:51
  • $\begingroup$ @kelalaka I heard there are theorems that describe how such budgets increase as a function of the other. E.g. for some algorithms maybe there is a theorem that if we'd like to reduce the timecpu budget, we'd need to square the space/ram budget (or something like it). Just an example. I am looking for such theorems. $\endgroup$ – caveman Nov 8 '20 at 3:51
  • $\begingroup$ Reason I ask this is because I think it relates to key derivation functions. $\endgroup$ – caveman Nov 8 '20 at 3:56

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.