Now before I'll post the question , I want to be clear. Technically , this WAS a homework question. BUT since I don't have to submit it (because I finished with the homework submitting process , and now studying for the test), I think it is legitimate to post here the homework file + I am doing it because I couldn't really solve it. (and there is no official solutions cuz our lecturers and his assistance are pretty god damn lazy:( )(adsbygoogle = window.adsbygoogle || []).push({});

now this is question 6 (with the hash table of size 2n to store n elements).

I've solved the first three sub-questions:

the first one is upper bounded by p=1/2 and it distributes as geometric random variable.

the second one is just substituting in the first sub question.

the third one is basically the sum of all n Xi insertions with the answer of sub question b.

Now, the forth questions deals somehow with Markov's inequality and about to prove that the expected length of probes is O(logn).

So I know that Markov's inequality means :

P(x>=t)<= E(X)/t

and although i tried to used this fact to get an upper bound , I couldn't find any solution or a lead.

Note: This is a new question which didn't appear on previous years assignments. If you have a reason to believe this question was made inappropriately or maybe even some mistakes.

Looking forward for your help

and thank you,

Aviv

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Hash Tables + probability question

**Physics Forums | Science Articles, Homework Help, Discussion**