2
$\begingroup$

I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially Savitch's theorem). I have a very strong intuition for time complexity, but I don't understand how space complexity fits into a heirarchy of time complexity, and I think it has to do with the fact that it is all discussed in terms of Turing machines. It is hard to see how space and time are related when I'm wasting time untangling convoluted algorithms described in terms of Turing machines.

Does anyone have any advice on how to think about Turing machines vis-a-vis contemporary computation in general? It is unintuitive to think about algorithms in terms of input strings, tapes, and machines simulating machines. I don't feel like I am leveraging my existing knowledge of computers and programming to more deeply understand the proofs and algorithms being presented.

I think I just need help understanding how space varies based on the data structure of the input. For some input of size $n$, are the bits required to represent each entity of the input negligible? Say our language is a set of objects that are all of a certain type, and each object is massive. How does space usage vary vs. a similar language with very small objects?

Edit: I understand now that space complexity fits in with time complexity because they are both resources used to determine whether some string is a member of a language; Or in other words, whether some element belongs to a particular problem (see here).

$\endgroup$
  • $\begingroup$ I'm not sure I understand. The time complexity of Turing machines is pretty horrible because they spend so many steps walking backwards and fowards along the tape. But the space complexity doesn't change much between Turing machines and other classical models of computation: there's some amount of data you need to store and that takes however much space it takes, whether it's written on a slow old Turing machine tape or in a spiffy random-access memory. $\endgroup$ – David Richerby Mar 18 '14 at 2:55
  • $\begingroup$ But don't you find it difficult to think in binary? When I think about space, I am thinking in terms of data structures (for RAM) and strings, not some alphabet $\Sigma = \{0,1\}$. The difficulty I am having has to do with the encoding of data, and how that translates to the usage of space. It does not seem so obvious to me, and perhaps that is because I have not studied encoding/compression and so it is not readily obvious to me how certain data structures are encoded on a Turing machine tape. $\endgroup$ – baffld Mar 18 '14 at 3:06
  • 1
    $\begingroup$ For Big-O, the encoding generally isn't too important. Remember that RAM is just a big array of 0s and 1s. Whether you store an integer as 32 or 64 bits doesn't matter as long as the size is fixed. For a data structure, you generally use some sort of recursive structure. Your base cases will usually be O(1), and then the structure will determine a recurrence relation for the overall size. The space complexity of the algorithm is just the added space complexity of all the data structures it needs to have going at any given time. $\endgroup$ – jmite Mar 18 '14 at 3:23
  • 1
    $\begingroup$ @baffld Binary doesn't make much difference: if you code numbers in decimal, it only takes three-and-a-bit times as much space and that constant is lost in the $O(-)$, anyway. I normally find it helps to consider Turing machines to be some slightly awkward machine-code-like language. $\endgroup$ – David Richerby Mar 18 '14 at 3:31
  • $\begingroup$ Are there any quick and dirty reads to get caught up on storage? What might be a good book if I wanted to understand how a Boolean formula (A binary tree?) is encoded in memory? $\endgroup$ – baffld Mar 18 '14 at 3:48
3
$\begingroup$

Space Complexity measures the amount of space it takes to carry out a specific task (as a function of the input size). It is very similar to time-complexity, that measures the amount of time it would take to complete the task. In both cases, the complexity highly depends on the specific model of machine (RAM machine is faster than a double-tape Turing Machine, which is in turn faster than a single-tape Turing Machine).

Let's now focus on a specific simple model: Single-tape TM.

Example: Sorting

Consider a simple task: say, sorting. The input is a list of numbers $x=\{a1, a2, ...\}$ and the machine should write them in order. The size of the input is $|x|=n$.

One way to perform this task on a single-tape Turing machine, is to perform a Merge Sort: we look at the first number $a1$, split the list into two list, one for numbers that are larger than $a1$ and the second list with the other numbers (and then we repeat it recursively).

But how do we implement "spitting the list into two" on a single-tape TM? A possible solution will mark the end of the input, then go over the list $n$ times, and every time it finds a number that should be on the second list, it will move it to the end of tape. So, if we started with $n$ numbers, now we have a list of $2n$ places (some of which will be empty, since we "moved" the numbers to somewhere else). If we continue with this naive approach, we will keep increasing the space in use more and more, and will get a very large space complexity (say $n^2$ if we stupidly double the space at each phase of the recursion).

But there is a more efficient way to do it: after creating two lists, we can "close the empty gaps" that occurred when we moved elements. Since we never add or remove elements, the same amount of space we started with is always big enough to keep the intermediate lists. For this approach we might need to maintain some counters that will tell us where each list begins and ends. Using smart methods, this can be done very efficiently, so that we will never use more than $\approx 2n$ cells of the tape. That is, the space complexity is $O(n)$ in this case. (see also In-place merge sort, which is not exactly what I was talking about, but might give you more intuition)

Now you can also see that Space and Time are related. If we perform the space-efficient variant, the TM needs to do some extra-work of "closing gaps", marking start and end points, keep track of counters, etc. This extra work takes time. It is very common that there is a tradeoff between space and time: if the algorithm is very fast, it takes a lot of memory, and if it is very space-efficient then it takes more time. For the task of sorting, see a table comparing the time and space complexity of various sorting algorithms. (Note that in that table they count the space complexity excluding the input).

Space complexity and its relation to Time complexity

So now we can define the space complexity of "sorting" as the minimal space it takes to sort. That is, take the most-efficient (memory-wise) sorting algorithm. How much space does it take to sort $n$ elements? This is the space complexity of sorting.

More generally, we can define classes of tasks that take the same space complexity. For instance $DSPACE(n)$ contains all the tasks that can be solved using $O(n)$ memory. Said differently, it contains all the tasks whose space-complexity is at most $O(n)$

There is a strict hierarchy here: If we know that a task needs $O(n)$ space, it clearly cannot be in $DSPACE(1)$. More accurately, for any function $f(n)$, $$ DSPACE( o(f(n)) \subsetneq DSPACE( f(n)).$$


Finally, we can relate time and space: $$DTIME (f(n)) \subseteq DSPACE(f(n)),$$ since in $x$ time we can access at most $x$ cells of the tape. More interestingly, we know that
$$DSPACE(f(n)) \subseteq DTIME(2^{O(f(n))}).$$ That is, whatever task that we can solve using $x$ bits of memory, we can also solve using in at most $2^{O(x)}$ time-steps. This follows since a machine with $x$ memory has maximal number of $2^{O(x)}$ different configurations, so if it doesn't go into an infinite loop it must end in less than $2^{O(x)}$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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