Create a hash table from array one elements. Search for elements form second table in the hash table. The time complexity depends on the hash function. You can achieve O(1) for searches in the optimal case (all elements will have different hash value), but O(n) in the worst case (all elements will have the same hash value). Total time complexity: O(n^x), where x is a factor of hash function efficiency (between 1 and 2).

Some hash functions are guaranteed to build a table with no collisions. But the building no longer takes strictly O(1) time for every element. It will be O(1) in most cases, but if the table is full or a collision is encountered, then the table needs to be rehashed – taking O(n) time. This happens not so often, much less frequently than clean adds. So the AMORTISED time complexity is O(1). We don’t care about some of the adds taking O(n) time, as long as the majority of adds takes O(1) time.

But even so, in an extreme case, the table must be rehashed every single insertion, so the strict time complexity would be O(n^2)

Advertisements