2
$\begingroup$

I'd like to know why when choosing how to optimize an algorithm that there almost always (always?) exists a time/space tradeoff.

Definition: https://simple.wikipedia.org/wiki/Space-time_tradeoff.

My favorite example is a karnaugh map for simplifying boolean logic. It abstracts boolean logic away with just clever geometry: enter image description here

Is there some sort of law from some mathematical theory to explain why this exists? Intuitively it seems to make sense, but the math would be nice.

Is this some property of information/computation? Is it guaranteed for any computation that can be performed? What about computations theoretically possible with infinite time, is a reciprocal guaranteed to exist that instead uses infinite space (or a middle ground that makes the time axis not go to infinity anymore)?

Improve this question
$\endgroup$
4
  • $\begingroup$ Well, I don't see a variant of trade-off for search (both binary and linear), so, it's not always possible. We assume no precalculations, of course. $\endgroup$
    – rus9384
    Commented Sep 22, 2017 at 17:00
  • $\begingroup$ Also, what is a tradeoff when working with Karnaugh maps? $\endgroup$
    – rus9384
    Commented Sep 22, 2017 at 17:02
  • $\begingroup$ Also, if something takes [at least] infinite time [in worst case], it also takes infinite space and vice versa for obvious reason. $\endgroup$
    – rus9384
    Commented Sep 22, 2017 at 17:10
  • 1
    $\begingroup$ I'm not sure what kind of answer you expect. Whenever optimizing more than one objective, it's common to have tradeoffs. This has nothing to do with computation. Another example is dining out, when you trade cost, quality, atmosphere, distance, and so on. $\endgroup$
    – Yuval Filmus
    Commented Sep 22, 2017 at 21:26

1 Answer 1

Reset to default
5
$\begingroup$

It doesn't. You're biased to results you find interesting.

If we measure a particular algorithm's space $s$ and time $t$ complexity, and then improve the algorithm. One of the following things can and does happen:

  1. We reduce $s$ and leave $t$ unchanged.
  2. We reduce $t$ and leave $s$ unchanged.
  3. We reduce both $s$ and $t$.
  4. We reduce $s$ and $t$ increases. WOW!
  5. We reduce $t$ and $s$ increases. WOW!

Now 1, 2 and 3 happen all the time. Why are you not asking for a "mathematical principle" for them?

Because they are boring. Since we strictly improved the algorithm it must mean the previous algorithm was suboptimal, and is immediately forgotten. Only in cases 4 and 5 we suddenly have two algorithms which do not have a clear winner, and only then do you start comparing them and wondering about a "mathematical principle" behind this difference.

What's happening is that given two objectives, you get a plot of possible solutions:

pareto frontier

Anything above and to the right of the critical red line is immediately forgotten as non-interesting, as there are algorithms that are strictly better in both $s$ and $t$. Your mind only looks at the red line (also known as the Pareto frontier), ignoring the rest of the plot.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.