CODEWITHSUNDEEP
c++algorithmspace-complexity
user8305079
user8305079

Reputation:

What is the space complexity of my code?

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.

Upvotes: 1

Views: 3615

Answers (6)

user2736738
user2736738

Reputation: 30926

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).

Upvotes: 3

molbdnilo
molbdnilo

Reputation: 66441

From a complexity point of view, the storage supply is limitless, and all that matters is how much of it you're using simultaneously.

Consider the problem of measuring X buckets of water.
It makes no differences to the space complexity whether you

  • Have one bucket that you fill, then empty, then fill again, then empty, ..., or
  • Fill one bucket and discard the bucket, then fill another bucket and throw that away, ...

since you're always using at most one bucket at any given time.
The buckets themselves don't count towards the complexity, only the amount of them you're simultaneously holding.

On the other hand, if you had not one, but X buckets that you fill (perhaps you want to save the water for the oncoming drought), the space complexity would be O(X).

Upvotes: 0

Riom
Riom

Reputation: 41

Space complexity tells you how much memory your algorithm is using.

In the second case you're only inserting one element into s. Right after that s goes out of scope and you start a new iteration. This means you're actually only using one memory unit at a time. Memory usage will not increase with n. Thus you have O(1).

Upvotes: 2

Mixhab
Mixhab

Reputation: 451

In the second case your complexity is O(1). Each iteration will use the set only once, and then it will be freed.

In general, the complexity depends on the total space your program requires. In your case you will use n times set of size 1, but it will not accumulate.

Upvotes: 1

Nasser Al-Shawwa
Nasser Al-Shawwa

Reputation: 3663

The space complexity is a measure of how the amount of required storage for your algorithm scales up in relation to your input size.

Assuming you insert n unique integers, std::unordered_map will indeed have to allocate enough storage to store n nodes, in addition to some constant values that are not affected by the number of integers you insert into it. Therefore, the space complexity would indeed be O(n).

In your second example, regardless of how many integers are in num, you will always allocate enough storage for one integer in a std::unordered_set. Therefore, your space complexity is O(1).

Upvotes: 0

Caleth
Caleth

Reputation: 63019

In the second case, each unordered_set ceases to exist after the loop body ends. A sensible implementation will re-use the same space for all the sets, and they only ever contain a single element.

If you use that as your space complexity metric, then the first case has O(n) additional space required, and the second case has O(1) additional space required

Upvotes: 0

Related Questions