4. Suppose we have n data items, and want to detect if there are any duplicates

Question

4. Suppose we have n data items, and want to detect if there are any duplicates among them.
Show how to do this in expected time O(n) using hashing. To do this, you may assume that
you have a universal family of hash functions that maps the data items into a number of slots
of your choosing. You may also assume that the operations of evaluating a hash function and
comparing if two items are equal takes constant time.
In specifying your algorithm, you should indicate how many slots m your hash table should
use (as a function of n), and then carefully prove that the overall expected running time is
O(n). You may use any results proved in class.

Explanation / Answer

let us think there are m(m would be some number) slots in hash table.as we know we can find out the slot using a hash function so time it would take is O(1).after we know the slot we should search the linked list attached to that slot.let us think there are n elements in the list and if the list is not sorted then we have to each and every element so it would take O(n) time. so total time=O(1)+O(n)=O(n) If the linked list is sorted then we can perform binary search so it would take O(logn) time so total time=O(1)+O(logn)=O(logn)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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