educative.io

Educative

Shouldn't the time complexity with hashing be O(n + m)?

Shouldn’t the time complexity for the hashing approach be O(n + m), where “n” is the size of the array and “m” is the size of the hash map?

The size of the hash map is only going to be the same as the size of the array, "n,"if there are no duplicates (best case), i.e. you can say that the overall time complexity is O(n). In any other case, the size of the hash map will be less than that of the array because of the nature of a frequency map, therefore the time complexity should be O(n + m).

Hi @Ron!

We are looking at the worst time complexity. As you said, the size of the hashmap is bounded by the size of the array, which means that m = O(n). In the worst case, the number of elements in both array and the hashmap would be the same(if there are no duplicates). In all other cases, m would always be smaller than n. Now, if we were to assume that m = n, then the time complexity would be O(n + n) => O(2n). We can take out the constant terms, and hence the time complexity would be O(n).