Most of the solutions posted using map claimed an O(N^2) algorithm, because they assume finding a key in a map takes constant time. Clearly, it may not be the case.

amortized key look-up in a hashmap in Java is O(1) time, even though the buckets can contain LinkedLists or Red-Black Trees. Please, explain your logic otherwise.