[prev] 19 [next]

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