CODEWITHSUNDEEP
algorithmspace-complexity
SPD
SPD

Reputation: 388

Space complexity when hashmap is used as a counter

Come across code like this:

void foo(const string& str) {
  unordered_map<char, unsigned int> m;
  for (char c: str) {
    ++m[c];
  }
}

What's the space complexity? if the answer is O(1), then what if the algorithm is to count the unique occurrence of 8-byte stream (or 16-byte 32-bye etc)? i.e. the upper bound of the problem space out sizes the memory space of a computer.

Upvotes: 1

Views: 400

Answers (2)

Jasmeet
Jasmeet

Reputation: 1460

The space complexity of your problem in O(length(str)).

As for the string, you are creating a new entry per new charachter met.

Now there are few things to be considered in your case : Is length of string greater than that of total charachter set defined by char data type.

If yes then space complexity is of O(total chars in char datatype) = O(1) else it is O(length(str)).

Same goes for utf-32 char type.

Now it completely depends on what your inputs are - If the inputs are of huge sizes, commonly greater than total size of char datatype or utf-32 size, the space complexity be considered as constant.

Upvotes: 1

Yash Shah
Yash Shah

Reputation: 1654

2,164,864 “characters” can be potentially coded by UTF-8.

So, if all the characters are present in a given string then the number of bytes used is 2,164,864 bytes (Supposing 1 byte per character).

As... 2,164,864 is also a constant. So in any case space complexity of the problem remains O(1).

O(1) signifies constant space.

Upvotes: 1

Related Questions