# Does space complexity analysis usually include output space?

Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this out just by reading examples.

If a function returns a new list, should the space complexity analysis of the function include the space required for the output? There seem to be clear reasons to want to exclude the input from the analysis, but it's less clear if the output should be excluded. Does the architecture of the system matter (e.g. multi-tape turing machine vs modern RAM-based computer)?

Consider the example functions below. They all use O(1) auxiliary space but different output space (relative to the input space), so the overall space complexity changes based on whether or not you include the output space.

generate a new list from a single int input:

int[] random1(int count) {
Random rand = new Random();
int[] output = new int[count];
for (int i = 0; i < count; i++) {
output[i] = rand.Next();
}
return output;
}


Output space: O(2^n)

generate a new list from a list input:

int[] random2(int[] input) {
Random rand = new Random();
int[] output = new int[input.Length];
for (int i = 0; i < input.Length; i++) {
output[i] = input[i] + rand.Next();
}
return output;
}


Size of output: O(n)

modify the input list in place

int[] random3(int[] input) {
Random rand = new Random();
for (int i = 0; i < input.Length; i++) {
input[i] = input[i] + rand.Next();
}
return input;
}


Size of output: O(1)

• Why is the first one O(2^n)? You generate a count-sized array, so it seems to me that it is just as linear as your second example. The fact that n is represented by an int instead of the size of an array is not relevant to describe the amount of memory your algorithm allocates. – andresp Dec 11 '19 at 22:04
• @andresp N is in terms of bits. If the input is a single 64-bit number, the output could be as many as 2^64 numbers, each of which is 64-bits long. – Kevin Kibler Dec 12 '19 at 0:13
• I guess that's correct if you use N as the number of bits, but it is not representative of the problem your algorithm solves. And if you want to follow that logic, in that case the int[] input in your second example is also either 32 bits or 64 bits as that is the size of the memory pointer being passed into your function. – andresp Dec 12 '19 at 0:45

Typically, we consider space complexity in terms of Turing machines with:

• one write-only output tape
• however many read-write working tapes you want.

The space usage is the number of cells used on the working tapes, so input and output space typically aren't counted. (See, e.g., Section 2.5 of Papadimitriou.)

Obviously, we don't want to count input space since, then, every algorithm would have to use linear space. Likewise, we don't want to count output space as that stops us from distinguishing between problems that are hard simply because the output is big (e.g., given an integer $n$, write the list $1, 2, \dots, n$) and problems that are hard because even computing a single output is hard (e.g., output a list of all $3$-colourings of the input graph).

On the other hand, not all authors do this. Sipser defines space usage as just the number of tape cells read by an ordinary Turing machine (Section 8) and the says, more or less, "Oops but that doesn't let us consider any kind of sublinear space, so we'd better redefine it not to include the input" (Section 8.4; he's only considering decision problems, so there's no output to worry about).

I'm not a fan of the redefinition approach but, either way, we need to exclude the input and output if we want to talk about any kind of sublinear space bound.

References