29
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – andresp
    Dec 11, 2019 at 22:04
  • $\begingroup$ @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. $\endgroup$ Dec 12, 2019 at 0:13
  • $\begingroup$ 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. $\endgroup$
    – andresp
    Dec 12, 2019 at 0:45

1 Answer 1

25
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ I think a more common space complexity analysis focus on the amount of memory allocated by the algorithm, rather than if it is used as output or not. If you discard output space you wouldn't be able to distinguish between example 2 and 3 here, i.e. from your perspective, in-place would be the same as making a complete copy of the input just as long as it was returned as output. $\endgroup$
    – andresp
    Dec 11, 2019 at 22:08
  • 1
    $\begingroup$ @andresp No, the usual way of formally analyzing space complexity is exactly as I've stated it. $\endgroup$ Dec 11, 2019 at 23:32
  • 2
    $\begingroup$ According to en.wikipedia.org/wiki/Space_complexity "It is the memory required by an algorithm to execute a program and produce output." $\endgroup$
    – andresp
    Dec 12, 2019 at 0:38
  • 2
    $\begingroup$ @andresp Please don't take the one-sentence summary at the top of a Wikipedia article as a formal definition. That part of the article is just trying to give a very broad idea of roughly what a term means, at the level of saying that a cat is "a small carnivorous mammal." You can't conclude from that statement that a dog is a cat, despite the fact that dogs are also small, carnivorous and mammals. $\endgroup$ Dec 12, 2019 at 9:45
  • 1
    $\begingroup$ Just found this other definition today: "That means how much memory, in the worst case, is needed at any point in the algorithm." courses.cs.northwestern.edu/311/html/space-complexity.html $\endgroup$
    – andresp
    Dec 31, 2019 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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