What is the space complexity of my code?

Question

I am comfortable enough with time complexities, but not yet with space complexities. I had the following question about space complexity:

unordered_set<int> s;
for(auto& i : nums)
    s.insert(i);

As per my understanding, the space complexity of the above code snippet is O(n) (n is the number of elements in the input vector nums) because I create the set outside the for loop and insert at max n elements in it.

However, if I would have created the set inside the for loop like:

for(auto& i : nums) {
    unordered_set<int> s;
    s.insert(i);
}

then in this case, would my space complexity again be O(n)? I understand what I am doing is different (creating a new set each time and inserting only one element in it), but I am just curious about the space complexity.

In short, does the space complexity depend only upon how many elements are inserted in the data structure, or also upon how many data structures are used (like creating them in a loop).

Thanks.

Answer 1

In the second case space complexity is O(1) and first case it is O(n).

Second case..

If you consider the second case in the loop each time you declare a local unordered_set and then you push 1 element. And then that is not used and again another iteration. At most 1 or constant amount of space is used.

First case..

In the first case you take a set and then insert elements. At most n elements you insert. That's why O(n).

Some definition

For every size of the input the algorithm will take the some amount of space. Without over complicating you can say that maybe it is used store the output or some work that you need to do intermediately. How many data structures you use is not the concern rather the space used by them is.

---

space complexity deals with finding out how much (extra)space would be required by the algorithm with change in the input size.

---

Now lets check one thing suppose you increase your number of input in first case from n=100 to n=100000 then what will the extra memory that you will need. As you will be seeing that it increases linearly. (Before 100 inputs 100 elements of set now 100000).

In the second case, do you need it? You are always using only 1 space.(Constant amount of space). And then you discard it. And in new iteration you work with another space. At once only 1 element is there. So whatever be the input it will always be same.

To be more clear, if you use in each iteration you insert 3 elements it doesn't change the space complexity..this will still be O(1) time complexity denoting that it uses constant amount of space (irrespective of the input size).