Does space complexity analysis usually include output space?

Question

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)

Answer 1

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

• one read-only input tape
• 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
C.H. Papadimitriou, Computational Complexity. Addison–Wesley, 1992.
M.  Sipser, Introduction to the Theory of Computation (3rd edition). Cengage Learning, 2013.