Looking for an example of proving space upper bounds for computing functions on a DTM

Question

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of the input string.

This to my mind looks like a work that can be done using only a linear amount of space on the work tape. All you really need to do is just have a counter to count the length of the input string in one pass and then you know what $\vert x \vert$ is and then squaring it is a constant time process and then just output those many $0$s.

Is my intutiion correct? How is one supposed to formally prove such a space-bound on the working of a (deterministic Turing Machine) DTM? Can someone kindly show how to write this up formally?

Answer 1

Perhaps the simplest way to show that a certain task can be done with small space is writing C-like pseudocode for it. If you are only using a constant number of variables, and each variable is exponentially bounded in terms of the input length (i.e. $|x| = O(k^n)$ for fixed $k$), then the resulting computation uses at most linear space. You can use the fact that addition, multiplication and division can be done in linear space ($O(n)$), as well as operations like determining the input length.

As an example, here is pseudocode for your algorithm:

f(x) {
  l = |x|;
  y = l * l;
  for i from 1 to y do:
    output 0;
}

The variables here are $l,y,i$ ($x$ is on the input tape so doesn't count). All operations are in linear space (as long as the inputs are small enough), $l \leq n$ and $y,i \leq n^2$, so the algorithm uses linear space.

If the bounds on the variables are polynomial ($O(n^k)$) rather than exponential ($O(k^n)$), then the resulting program is logspace (uses $O(\log n)$ space); all operations mentioned can be implemented in logspace. Indeed, since the bounds in your case are polynomial, your algorithm is logspace; the fact that the output is larger doesn't matter, since we only count space on the work tape.