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
You should probably read this
Thank you Sir :-)