22
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`
Example: a third of the elements have key
k
⇒ expected number of iterations = 3
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}