Consider the following algorithm that takes as input an array A and returns A with all the duplicate elements removed.
Example: A = {1, 4, 3, 1, 4, 5}, the algorithm returns {1, 3, 4, 5}
Algorithm:
Remove Duplicates
SetArray = new empty set
Arr = new dynamic array
for each element e in input array A
if not SetArray.contains(e) then
SetArray.add(e)
Arr.add(e)
return Arr
What will be the order of growth of this algorithm in the following cases?
(i) The set SetArray is implemented using a red-black tree
(ii) The set SetArray is implemented as a hash table using linear probing? (we use efficient hash function)