I'm finding contradictory information online where some places only consider auxiliary space and others define it as
Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.
What parts of a function are used in space complexity? Does it include input, output, and auxiliary space?
For example, consider the following function:
vector<int> mult2(vector<int> nums)
{
vector<int> result;
for (int i=0; i < nums.size(); i++)
{
result.push_back(2*nums[i]);
}
return result;
}
Then the space complexity would be:
If $n$ is the size of input (nums), then there is nums and result of size $n$ each or $2n$. Along with constant auxiliary space for int i.
In other words, $O(2n+1)$ or $O(n)$, where $n$ is size of input (nums).
In the case of the input nums being passed by reference would it then not be counted in the space complexity?
Edit Seems the confusion is generally around if the input is included or not.
Example 2:
int sum(vector<int> nums)
{
int sum = 0;
for ( auto n : nums )
sum += n;
return sum;
}
Is the space complexity O(n) or O(1)?