There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching results that are computed or fetched from some storage increases memory use but avoids repeating the same time-consuming task. Compressing arbitrary data without information loss tends to take longer the closer you want to get to its implicit limit for entropy.

But besides that, trade-offs seem to occur throughout almost every level of computing: the theory behind algorithms and data structures, hardware, programming, all the way up to project management. I'm wondering if there's some fundamental principle underlying this that makes trade-offs inescapable.

For specific cases I can see why trade-offs exist. Data structures could in abstraction be seen as cached versions of some algorithm's execution. The work is done up-front and the result kept in memory, with the trade-off being some overhead for managing the structure. A hashmap allows fast lookup by a key (constant time) rather than having to traverse all elements in a collection (linear time) because the "look-up" work has been done up-front when adding something to the map. Purely functional data structures supply some insight in the relation between data structures and algorithms. But for a CPU cache, for example, I don't know why the cache can't be made as big as the RAM memory and as fast as a typical cache; is it physical constraints, or simply cost? And regardless of which it is, why does the trade-off exist?

So my question is whether these various trade-offs seen in computing are simply analogues and the trade-offs in memory use/computing time and those in cache size/speed are the same things in different guises, or if they're distinct things. And if various trade-offs are distinct cases, is there some fundamental, deeper reason why trade-offs exist? Is there some reason why something always has to give in one place in order to receive in another? Is it some basic aspect of information theory, of physics? And are there cases where we can "have our cake and eat it" and optimize everything?

Sorry if the question comes across a bit as philosophical, but I've found it's hard to research something if you don't first have the right name for it. And in information theory some problems turn out to be variations of one another, or can be reduced to some fundamental concept (e.g. computability/Turing machine).

  • $\begingroup$ Every object can be measured on many scales -- that's just a fact of life. Not sure if there's anything special about trade-offs in CS. $\endgroup$ – Raphael Apr 27 '17 at 18:09
  • $\begingroup$ Welcome to CS.SE! This sounds too broad to me; there are many tradeoffs in CS, and there might be different fundamental principles underlying different tradeoffs. (Any community votes about whether the question is suitable for our site format?) Anyway, I think it might work better if you asked a new question about a specific tradeoff that you want to understand. Ultimately, a lot of things probably come down to "cost". $\endgroup$ – D.W. Apr 27 '17 at 18:09

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.