I often heard that using data structures help to reduce (time or space) complexity of some operations.

  1. I wonder if that is achieved at the cost of something else?
  2. When solving a problem, is something still conserved, over all choices of data structures and algorithms, just like the conservation of energy? Such as some kind of overall (time or space) complexity of an algorithms and a data structure being used?
  • 2
    $\begingroup$ This question is too broad as it is. The answer to 1. seems to be trivially "yes" (with the knowledge of an introductory course in algorithms/data structures). The answer to 2. may be complexity theory as a field, but it's hard to tell since the question is so vague. Can you focus your question wiht an example? $\endgroup$ – Raphael Oct 5 '14 at 17:28

To represent a collection of integers, you can use an array with one word of memory per element. For instance, say $A = [0,1,7,10]$. Alternatively, you could use an array $B$ to represent the same collection in the obvious way: $B = [1,1,0,0,0,0,0,1,0,0,1]$. Searching for element $x$ in $A$ takes $\Theta(n)$ time (or perhaps just logarithmic time if $A$ is indeed sorted), but you can do the same in $B$ in $O(1)$ time by just looking at $B[x]$, i.e. just indexing $B$ at position $x$. This is a tradeoff: by using more memory for $B$, you get faster lookups. Time-memory tradeoffs like this are often encountered.

Sometimes, one can show that to solve a problem, you must always no matter what spend some time, memory, or other resource to solve it. In such results, one must always specify the model of computation used. For instance, there is a well-known decision tree lower bound of $\Omega(n \log n)$ for sorting. So in this model, you absolutely can't beat this bound no matter what you do.


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