I implemented the same idea as the editorial in 3 different ways.

**Using stl:map :** submission

**Using stl:unordered_map:** submission

**Using stl:lower_bound:** submission

I have no idea why **map** would give **TLE** and **lower_bound** will not, both costs **O(logn)**. Given that **lower_bound** solution passes in just **312 ms**, I expect **map** solution to pass even if runtime is a bit higher. And why on earth would **unordered_map** give a runtime of **1341 ms**? It was supposed to be of **O(1)** cost. I am certain my hash_function has absolutely no chance of colliding.

Can anybody explain this behaviour...

I stumbled upon the exact same problem few weeks ago in a different OJ. Here is the translated version of the answer that I received.

Because N is rarely infinitely large in the real world, the difference between O(lgN) and O(1) is varies by constants attached to the time complexity depending on the size of N.

For example, let's say there's a hypothetical problem where you have to find the number you want with the least comparison.

If there is an O(1) algorithm that always looks for numbers by 50 comparisons, regardless of N, and an O(lgN) algorithm that compares ceil(lgN) times against N,

In terms of complexity alone, O(lgN) is faster than O(1) unless N is bigger than 1e15 or so.

This happens often, even when there is a significant difference in time complexity, such as O(N) and O(N^2).

If you want to know where the time complexity of hashmap, especially the unordered_map of C++, has a big constant, check the following videos and links.

unordered_map

hashtable_policy.h

bits/hashtable.h