How to calculate the spatial complexity of a function?

Question

I understood the basic one, if I have a function like this:

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

parameters require 3 units of space and 1 for a local variable, and this never changes, therefore it 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] } } 

This requires N units for a , units M for b and units L for c and 1 units for i and n . Thus, storage will require N+M+L+1+1 .

So what will be big-O for cosmic complexity here? The one that takes up higher memory? That is, if N takes a higher speed than M and L (out of much higher values, more than 10**6 allowed) - it is so safe to say that the complexity of the space is O(N) or not the way we do for time complexity ?

But if all three ie a, b, c are not very different from each other

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 spatial complexity? O(N+M+L) ? Or the biggest one?

Answer 1

The complexity of the algorithm space or data structure is the maximum amount of space used at any given time, ignoring the space used by the input for the algorithm. Therefore, the spatial complexity of all three examples in your question is O (1)

Answer 2

When we talk about the complexity of space, we do not consider the space used by the input.

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

The standard Turing multi-tape machine for determining the complexity of space also does not take into account the output.

The input is read-only, and the output is write-only and does not take into account the complexity of the space.

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