Substituting, k = lg (n + 1) we have
Now combining both the terms we have,
AElementPresent (n) =  [ ]
Given that: p ≡ Pr (element exist in the array)
A (n) = p(average cost when element is present) + (1 – p) (worst cost)
= p[] + (1 – p) [lg(n+1)]
For example, if n = 1023,
A(n) = p[lg(1024) – 0.7213 +  + (1 – p)[lg(1024)
= p(9.3) + (1 – p)(10)
Share with your friends: |
