Please don\'t forget that this is dictionary implementation specific! Also, some

Question

Please don't forget that this is dictionary implementation specific! Also, some work (don't have to show work for every single thing you do) would be nice.

Many algorithms need only the ability to insert elements into, delete elements from, and test membership in a set. A dynamic set that supports these operations is a dictionary. Fill in the following table with the average-case and worst-case efficiency classes for four implementations of a dictionary. Be sure to state any assumptions you make about any of the data structures!

Explanation / Answer

           Unordered Array Ordered Array Binary Search Tree HasTable
Average Worst   Average Worst Average Worst     Average Worst
Insertion O(n) O(n) O(logn) O(n) O(logn) O(logn) O(logn) O(logn)

Deletion O(n) O(n) O(logn) O(logn) O(logn) O(logn) O(logn) O(logn)

Search O(n) O(n) O(logn) O(n) O(logn) O(logn) O(logn) PO(logn)
  
          

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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