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)
