Consider the Unique algorithm below, which takes an input array data of length n
ID: 3585445 • Letter: C
Question
Consider the Unique algorithm below, which takes an input array data of length n and returns all of the elements that appear in data, with duplicates removed Input: data: array of characters Input: n: length of data Output: array containing every element of data, with duplicates removed 1 Algorithm: Unique 2 dict = Dictionary(data) 3 prev=dict,Min() 4 next = prev·Successor(prev) 6 while next NIL do if next prev then Add next to unq 8 9end 10 prev next 11 | next=dict·Successor(prev 12 end 13 return unq Answer the following questions about Unique: 1. What is the worst-case time complexity for Unique when implementing dict as a balanced BST? Show your work What is the worst-case con dict as a sorted array? Show your work. time complexity for Unique when implementin 3. Compare and contrast these two implementations, and indicate which you would recommendExplanation / Answer
Few points about BST:
1) Inorder traversal gives sorted array. As per algorithm, we have to access from dictionary directly. So, this option is ruled out.
2) So, there is time consumption to get the node data and it will be O(n) in worth case.
Sorted Array:
1) As we knoe array elements get stored in sequential manner in memory. So, accessing will be fast.
2) Accessing element in worst case is also O(n)
Answer:
while next != NIL do
if next != prev then
Add next to unq //Time comeplexity = 1
end
prev = next;
next = dict.Successor(prev); //Main step for calculating time complexity
end
So, accessing element is the main step for calculating the time complexity.
1) Worst time complexity = O(n);
2) Worst time complexity = O(n);
3) Now choosing algorithm depends on following factor:
a) How frequent insertion happens
b) How frequent deletion happens
c) Lookup operation
BST has O(log(n)) lookups, inserts, and removals
sorted array has O(log(n)) lookups and O(n) inserts and removals
So, if insertion and deletion are frequent then we must go with BST else we can go ahead with sorted array