Please don\'t forget that this is dictionary implementation specific! Also, some
ID: 3677628 • Letter: P
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)