2
$\begingroup$

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)?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

We usually don't count the input as part of the space used by a procedure.

In your case, however, this makes no difference, since $O(2n+1)$ and $O(n)$ are the same.

Whether you pass the vector as reference or not, what is copied is only a pointer to the underlying array. If, instead, the vector was passed by creating a fresh copy, then it would make sense to count it somewhere — possibly at the caller's expense rather than at the callee's expense. This is a convention which is up to you to decide.

$\endgroup$
3
  • $\begingroup$ In this answer: cs.stackexchange.com/a/108512/129684 it also mentions "Space Complexity is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity includes input size.". Is it that input size is also included but it is masked by the Big-O notation (asymptotic space) 2n=>n? $\endgroup$
    – worbel
    Jun 17, 2021 at 17:06
  • 1
    $\begingroup$ At a final count, space complexity is a way to determine how much memory your program will need. You can accomplish this in many ways. Choose the way which is most convenient for you, or which is standard in your field. $\endgroup$ Jun 17, 2021 at 17:30
  • $\begingroup$ Ah ok, I thought the concept was standard across CS fields. It seems that the only thing in question here is if 'input' is included in the space complexity. I think agree with the idea not to include the input. For example, if you look at my "Example 2" it makes more sense to consider this function as a constant space complexity and not linear. It could be the case that the read-only nums is passed by reference (or maybe the compiler is smart to do so). Then the memory would reside in the caller's scope and not callee's scope. $\endgroup$
    – worbel
    Jun 17, 2021 at 20:54

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.