CODEWITHSUNDEEP
data-structuresbig-ohashtable
youhana
youhana

Reputation: 328

what is the Big O of insertion in Hashtable inside loop?

Considering Hashtable without collisions ..

If I have this snippet of code

for(int i=0;i<jewels.length();i++) #step 1
        jewelSet.add(jewels.charAt(i)); #step 2

Step 1 Big O is O(n) .. okay that's fine

Step 2 Big O individually without loop is Big(1), that's correct...

My question .. Step 2 in the loop will result in O(1) * n .. means .. O(n)

So this entire code posted Big O will be O(2n) = O(n) ..is this correct or not?

I mean .. when

Loop :
      O(1)

After many loops .. O(1) total sum will not still O(1) .. it will be n * O(1) .. correct ???

So even if it's constant BigO, but when it's inside number of loops, it will cost the entire code algorithm to be the number of loops * BigO(1) .. results in BigO(n)

Upvotes: 0

Views: 65

Answers (1)

Devendra Kumbhkar
Devendra Kumbhkar

Reputation: 285

When we calculate the complexity we eliminate smaller factors in the formula because, for large/infinite input, smaller factors O(1) will be negligible as compared to O(n) that why the time complexity for the above algorithm will be O(n) only.

Upvotes: 1

Related Questions