Suppose you insert() an item into a hashtable and then immediately do a lookup()

Question

Suppose you insert() an item into a hashtable and then immediately do a
lookup() on that item as the methods shown below. What is the worst-case complexity of the program in this
situation? Briefly explain the answer please. Thanks!

public void insert(T item) { int initSize = tableSize; if (hashTable == null) { throw new NullPointerException(); // hash index int hashIndex = hashTable.hashCode() % initSize; if (hashIndex loadFactor || (hashTable[hashIndex]).size() + 1 > maxChainLength && maxChainLength > 1) { // resize tableSize = initSize * 2 + 1; // new table with new size newTable = (LinkedList[] (new LinkedList[tableSize]); // go through all items in old table for (LinkedList 1 : hashTable) {

Explanation / Answer

For any search, the worst-case running time occurs when the desired item is not in the array.

The worst-case lookup time in hash table schemes is O(n)

Explaination:

When you have inserted the element, a hash index is assigned to it and lets say it lies at position n in the list.

Now, in the lookup function, we are accessing each element and check if it is equal to the item we are looking for. Hence, nth item will be found after checking n values. Hence it will be n.

Even if the element is not present in the array then, n is total number of elements in the list, as we iterate over full list to find the element.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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