Analysis of Randomised Algorithms (cont)
Analysis:
- p … ratio of elements in L with key k (e.g. `p=1/3`)
- Probability of success: 1 (if p > 0)
- Expected runtime: `1/p` ( = `lim_(n rarr oo)sum_(i=1..n)i*(1-p)^(i-1)*p` )
- Example: a third of the elements have key k ⇒ expected number of iterations = 3
|