Question

How to calculate space complexity of an algorithm?

Answer 1

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?