670 views
0 votes
0 votes
Consider an open address hash table with uniform hashing. What is the time complexity of sucessfull search ?

(A)O($\alpha$$^{2}$)

(B)O($\alpha$)

(C)O(1-$\alpha$)

(D)O(1/1-$\alpha$)

1 Answer

Best answer
2 votes
2 votes

When hashing n items into a hash table with k slots

The main statistic for a hash table is the load factor: α=n/k

We can visualize this by following statement and the graph.

The length of probe sequence is proportional to α/(1−α). As the load factor α approaches 1, probe times goes to infinite.

So the time complexity would be O(1/1-α)

selected by

Related questions

0 votes
0 votes
0 answers
2
Rahul_Rathod_ asked Dec 28, 2018
413 views
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
1 votes
1 votes
0 answers
3
hrcule asked Aug 9, 2018
501 views
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is us...