From: Scott Brickner <sjb@austin.ibm.com> % k-space random sequential percent searched method method difference [...] 99.9 115892899 16760439 591
But you fail to take into account the probability that the search will have to go that far. This is how I compute the expected cost of the random search. The probability of finding the key upon searching the k-th segment is: k-1 p(k) = (1 - 1/n) . 1/n The expected cost is the sum of all possible costs, weighted by their probability: ___ ___ \ \ i-1 e = > i p(i) = 1/n > i (1 - 1/n) /__ /__ i = 1..oo i = 1..oo ___ ___ \ \ i-1 = 1/n > > (1 - 1/n) /__ /__ i = 1..oo j = 1..i ___ \ i-1 = 1/n > (1 - 1/n) /__ {(i,j) | 1 <= j <= i} ___ ___ \ \ i-1 = 1/n > > (1 - 1/n) /__ /__ j = 1..oo i = j..oo ___ ___ \ j-1 \ i = 1/n > (1 - 1/n) . > (1 - 1/n) /__ /__ j = 1..oo i = 0..oo \_______________/ \_______________/ n n e = n This means that if you do many random searches (with a good RNG), the average cost of one search must be n. Any errors in the above ? -- Damien