The ADT known as a \"dictionary\" provides a way to look up with keys to find va
ID: 3830621 • Letter: T
Question
The ADT known as a "dictionary" provides a way to look up with keys to find values. We define these operations as: lookup(key) which returns either a value, or a "not-found" indicator. remove(key) which removes the item with that key (if it exists). insert(key, value) which adds the new key-value pair, or replaces the value if it already exists. We could implement a dictionary with an array of (key, value) pairs, sorted by key. We could use binary search for lookup. We'd have to figure out a way to put new values into the sorted list, and remove values. Or we could use hashing. a. If we use binary search on a sorted array, what is the worst case time for lookup(key) in terms of big-o. (No explanation needed, just state the answer.) b. If we use binary search on a sorted array, what is the worst case time for remove(key)? This time, briefly explain your answer. c. If we use binary search on a sorted array, what is the worst case time for insert(key, value)?This time, briefly explain your answer. d. If we use hash tables instead, what is the worst-case big-O time for lookup(key)? (Just state it.) e. Is the worst case for lookup(key) for hash tables better or worse than for the binary search? f If we use hash tables instead, what is the average (expected) case big-O time for lookup(key). (Just state it.) g. Is the average (expected) case for lookup(key)for hash tables better or worse than the binary search approach?Explanation / Answer
Answer a) if we use binary search on a sorted array, O(n) is the worst case time for lookup(key).
Answer b) if we use binary search on a sorted array, O(n) is the worst case time for remove a key.
In worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of delete operation may become O(n).
Answer c) The worst case time complexity of insert operations is O(h) where h is height of Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of insert operation may become O(n).
Answer d) if we use hash tables, O(n) is the worst case time for lookup(key).
Answer e) both are same.
Answer f) if we use hash tables, O(1) is the Average case time for lookup(key).
Answer g) hash tables average case is better than the binary search.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.