CODEWITHSUNDEEP
javahashmapspace-complexity
here_to_learn
here_to_learn

Reputation: 203

Space Complexity of HashMap when iterating over an Array in linear time

I have a doubt regarding the space complexity of a program. Let's say I am iterating over an Array (stores event ids) with a size of n (may be in billions). I wanted to track the occurrence of each event id, so I have used a hash map to store event id as key and its occurrence counter as value.

Here is the pseudo code:

Map m =  HashMap<>
for i to n-1
  if m.contains(i)
     int prevCount =  m.get(i)
     m.put(i, prevCount +1)
  else
   m.put(i, 1)

What would be the space complexity?

PS This is my first question in stackoverflow, if it seems duplicate, please route me to the correct answer.

Upvotes: 1

Views: 2831

Answers (1)

Eran
Eran

Reputation: 394026

Your loop adds at most n-1 key/value pairs to the HashMap.

Therefore, the space complexity is O(n), since the HashMap internal storage consists of an array whose size would reach a power of 2 close to n (assuming you didn't give the HashMap an initial capacity that is much larger than n), and each element of the array is a linked list with an O(1) average number of elements.

Upvotes: 3

Related Questions