Consider two sets of integers S s1 s2 sm and T t1 t2 tn

Consider two sets of integers, S = {s1, s2, ..., sm} and T = {t1, t2, ..., tn}, m n.

(a) Propose an algorithm (only pseudo-code) that uses a hash table of size m to test whether S is a subset of T.

(b) What is the average running time complexity of your algorithm?

Solution

1. Algo   Subset (S, T):

Input: Arrays S and T of integers

Output: True if S is a subset of T

          for i <- 1 to n

               hash_table.insert(T[n])

           for i <- 1 to m

               if (!hash_table.find(S[m]))

                return false

       return true;

2. Running time: O(n+m)    O(m) for building the hash table, O(1*n) for searching through the hash table .