Mridul323's blog

By Mridul323, history, 3 years ago, In English

Hello Codeforces!

Recently I was trying to solve problem 1102E - Monotonic Renumeration

I tried submitting my solution 100299607 using unordered_map and got TLE on test 47. Then I went thorough the other solutions and found that people have solved it using map. I submitted same code again 100299556 using map and this got Accepted.

I used to think that unordered_map is always faster than the map. I googled and then get to know that search time of map is O(log(n)) while search time of unordered_map in O(1) and in worst case its O(n).

Internally unordered_map is implemented using Hash Table so how the search time can take O(n) in worst case?

Somebody please clear my doubt.

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You should probably read this