- #1
FlashStorm
- 17
- 0
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 because our lecturers and his assistance are pretty god damn lazy:( )
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
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