Question

What is the average retrieval time when n keys hash to the same slot?

(a) Theta(n)

(b) Theta(n^2)

(c) Theta(nlog n)

(d) Big-Oh(n^2)

My doubt is from Hash Tables in portion Hash Tables of Data Structures & Algorithms I

The question was posed to me in unit test.

Answer 1

The correct option is (a) Theta(n)

Easy explanation - The average retrieval time when n keys hash to the same slot is given by Theta(n) as the collision occurs in the hash table.