Linear Probing: Analysis Expected number of Example (λ = 0.5) probes for insertion or Insert / unsuccessful search unsuccessful search 2.5 probes 1 1 + Successful search 2 1 2 (1− λ) 1.5 probes Expected number of Example (λ = 0.9) probes for successful Insert / search unsuccessful search 1 1 50.5 probes + Successful search 1 5.5 probes 2 (1− λ) 22
Linear Probing: Analysis Expected number of probes for insertion or unsuccessful search 1 1 + 2 2 1 (1− λ) Expected number of probes for successful search 1 1 + 2 1 (1− λ) Example (λ = 0.5) Insert / unsuccessful search 2.5 probes Successful search 1.5 probes Example (λ = 0.9) Insert / unsuccessful search 50.5 probes Successful search 5.5 probes 22
ADS-RSD-UNIT-2.docx