Array subset using hashing

Question

To check if arr2 is subset. Input: arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1} Output: arr2[] is a subset of arr1[]

If we use linear probing. Hashtable will look like: {0=7, 1=1, 2=13, 3=21, 4=3, 5=11} where first item is index(hashed code) second is value If you see for element 7. Hash code is 7%6=1. So from 1 it has to traverse complete hashtable by checking every bucket. Here Time Complexity is O(n)

Later on we will be searching all elements in arr2 with hashtable.

So overall time complexity will be Len(arr2)*O(n).

What is the benefit of hashing then?

Answer 1

The best-case complexity of search operation in hash table is not O(n), but O(1). So in best case you will get complexity Len(arr2) * O(1) => Len(arr2), and we can treat it as O(1). On the other hand, the worst-case complexity is really O(n). So, you should look at amortized cost of entire algorithm, that will be lower, than O(n)