How to calculate the space complexity of function?

Question

I understood the basic that if I have a function like this:

int sum(int x, int y, int z) {
  int r = x + y + z;
  return r;
}

it requires 3 units of space for the parameters and 1 for the local variable, and this never changes, so this is O(1).

But what if I have a function like this:

void add(int a[], int b[], int c[], int n) {
    for (int i = 0; i < n; ++i) {
        c[i] = a[i] + b[0]
    }
}

Which requires N units for a, M units for b and L units for c and 1 unit for i and n. So it will need N+M+L+1+1 amount of storage.

So what will the big-O for space complexity here? The one which takes higher memory? I.e. if N takes more higher momery than M and L (from much higher means suppose larger than 10**6) - so is it safe to say space complexity is O(N) or not like we do for time complexity ?

But if all three i.e a, b, c are not very much different

Like this function

void multiply(int a[], int b[], int c[][], int n) { 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            c[i] = a[i] + b[j];
        }
    }
}

Then what will be the space complexity? O(N+M+L)? Or still the biggest one?

Answer 1

When we talk about space complexity, we don't consider the space used by the input.

This allows us to talk about algorithms which are constant space, O(log n) space etc. If we started counting the input, then all algorithms will be at least linear space!

The standard multi-tape Turing machine definition of space complexity also does not count the output.

The input is read only and output is write only and do not count towards the space complexity.

So to answer your question: look for what memory your method allocates, including stack space for recursion/local variables etc, and that will determine the space complexity.