[prev] 24 [next]

Analysis of Randomised Algorithms (cont)

Analysis:
  • p … ratio of elements in L with key k
  • d … maximum number of attempts
  • Probability of success: 1 - (1-p)d
  • Expected runtime: `(sum_(i=1..d-1)i*(1-p)^(i-1)*p)+d*(1-p)^(d-1)`
    • O(1) if d is a constant