Question

DEPTH counting starts at 1 at the root.

What should the loading factor be (on ANY HASH TABLE) if you want to have an average of 1.4 comparisons per successful search if LINEAR PROBING?

Answer 1

Required average number of comparisons per successful search = 1.4

We know in linear probing, average number of comparisons = (1/2) (1 + (1/(1 - )))

Where, = loading factor

average number of comparisons = (1/2) * (1 + (1/(1 - )))

or, 1.4 = (1/2) * (1 + (1/(1 - )))

or, 1.4 = (1/2) * ((1 * (1 - ) + 1)/(1 - ))

or, 1.4 = (1/2) * ((1 - + 1) / (1 - ))

or, 2.8 = (2 - ) / (1 - )

or, 2 - = 2.8 - 2.8

or, 1.8 = 2.8 - 2

or, 1.8 = 0.8

or, = 0.444

So, the loading factor for the hash table = 0.444.

Please comment in case of any doubt.
Please upvote if this helps.