Consider the Unique algorithm below, which takes an input array data of length n

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 character Input: n: length of data Output: array containing every element of data, with duplicates removed 1 Algorithm: Unique 2 dict= Dictionary(data) a prev - dict.Min() 4 next-prev .Successor(prev 5 unq= {prev 6 While next * NIL do 7 | If next prev then 8 9end 10 | prev= next 11 | next-dict.Successoripreu) 12 end 13 return unq Add nert to 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 2. What is the worst-case time complexity for Unique when implementing dict as a sorted array? Show your work 3. Compare and contrast these two implementations, and indicate which you wouldd recommend

Explanation / Answer

1. A balanced BST has a natural ordering. The nodes in the left subtree are less than or equal to the parent node and the nodes in the right subtree are greater that the parent node.

Since our goal is to remove duplicate characters and output only the distinct characters, having a BST doesn't provide any advantage. The call to find the Min() will take O(log n) time where n is the number of characters in the array. Similarly the calls to Successor() may take O(log n) time in the worst cases.
So the worst case time complexity is O(n*log n). Also the preporocessing time for building a balanced BST is O(n*log n).

2. Having a sorted array in ascending order is very much beneficial since MIn() takes O(1) time and each call to Successor() takes only O(1) time. Therefore total running time is O(n). The preporocessing time for sorting is O(n*log n).

3. Comparing the time complexities excluding the preprocessing times of the two approaches, it will be recommended to use a sorted array for implementing the dict.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.