How do you calculate spatial complexity?

Hello

I am trying to understand how to calculate the Big O, but for the spatial complexity, I did not find enough information to undertand this topic, can someone explain me?.

All I just found is this:

Space complexity describes how much space your program
needs. Since foo does not declare arrays, each level
requires O(1) space. Now all you need to do is to figure
out how many nested levels can be active at the most at any
given time.

But I dont understand can someone explain how to calculate for a given code? help very appreciated

1 Like

Suppose you are having only simple variables, then, irrespective of the number of inputs, you use only constant amount of memory (or space). So, space complexity is O(1).

However, if you have some data structures like a 1D-array, designed to hold N elements, where N can vary from input-to-input, then the amount of memory required is dependent on N. When N is small, the space required is also small. When N is large, then space required is also large. So, there is a linear dependence on the space required and the input size. That is O(N) space.

Similarly, if you have a 2D-array of size NxN, then generally, the space required is O(N2).

As an example, consider the problem of finding the minimum of N (> 0) positive integers.

int N;
cin >> N;
int array[N];
for (i = 0; i < N; ++i)
{
    cin >> array[i];
}
int minimum = array[0];
for (i = 1; i < N; ++i)
{
    if (array[i] < minimum)
        minimum = array[i];
}
cout << minimum;

Here, we are having an array, whose size varies with N. Total space requirement = 2 + N, where 2 is for the variables N and minimum (each take one location each) and N is for the array. So, the space complexity of this algorithm is O(N).

However, consider another solution:

int N;
cin >> N;
int minimum, tmp;
cin >> minimum;
for (i = 1; i < N; ++i)
{
    cin >> tmp;
    if (tmp < minimum)
        minimum = tmp;
}
cout << minimum;

Here, total space requirement is 3, one location each for the variables N, tmp and minimum. So, the space complexity is O(1) or constant.

I hope this was what you were looking for.

1 Like

Thank you very much for answering, another question If I use an arraylist or a vector will be O(n)?

Yep. It will be.

And a vector of vectors (or an arraylist of arraylists) is generally O(N2)

thanks @tijoforyou understood

1 Like