CODEWITHSUNDEEP
algorithm
Snowball
Snowball

Reputation: 1238

Expected runtime of hashing with chaining, but with each list in sorted order

This is a question from CLRS page 261 (11.2-3).

Suppose we implement a hash table with chaining, and keep each list in sorted order. Assuming simple uniform hashing, what is the expected run time for insertions, deletions, successful searches, and unsuccessful searches?

It says here that both kinds of searches become expected runtime of theta(1+log(alpha)). Insertions and deletions stay theta(1+alpha) because the time to insert into or delete from a sorted list is linear.

(Note that alpha represents the load factor, or the number of total keys stored divided by the number of table slots)

Question: It seems to me that insertions and deletions should take 1+log(alpha) time on average. 1 for the computation of the hash function. log(alpha) since each linked list in a slot has expected length of alpha, and we can divide and conquer to find the location of insert in log(alpha) time. However, the answer says theta(1+alpha).

Then I thought, perhaps the answer is assuming you don't divide and conquer, and just search linearly through the list. But then I don't understand why an unsuccessful search take theta(1+log(alpha)) time, since if we have to search linearly, then the time is proportional to the size of the list, alpha, so the search time should be theta(1+alpha). This provides no improvement over hashing with chaining with no sorting involved.

What am I misunderstanding here?

Upvotes: 1

Views: 1072

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

The complexities given are correct if each slot has a sorted array list instead of a linked list -- searching in the list takes O(log n) time with binary search, but insertion or deletion takes O(n), because it requires shifting all the elements after the insertion/deletion point up or down.

If a linked list is used, then search, insert, and delete all take O(n) time, because you can't do a binary search without random access.

Upvotes: 1

Related Questions