My attempt:

I need to find exected number of probes in case of successful search. I am assuming, n elements and m slots in hash table

E(# of probes) = average of {1st probe success , 2nd probe success, .... nth probe success} over n

$i^{th}$ probe success = $(i-1)$ probes unsuccessful and ith probe successful = probability that (i-1) probes unsuccesful and last probe successful = $(\alpha^{(i-1)})* \alpha$ --> Is this correct???

I am taking, probability that i-1 slots are filled up and those elements inside them are not equal to key k(unsuccesful) = $(\alpha^{(i-1)})$

taking forward,

E(# of probes) = $\frac{1}{n} \sum_{i=1}^n i*\alpha^i \neq \frac{1}{\alpha} \ln \frac{1}{1-\alpha}$

Please point my mistake....

  • $\begingroup$ can any 1 please tell me where i committed mistake rather than just downvoting it? $\endgroup$ – Nascimento de Cos Nov 14 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.