Is sequential or random comparison more efficient?

Question

I am wondering (purely out of curiosity) if it is more efficient to compare numbers sequentially or randomly. I initially thought that it would be more efficient to compare numbers sequentially, but I was not sure and I have know idea how I would go about figuring this out, so I figured that I would ask the community.

Here is some pseudo code to help explain what I am thinking:

Sequential:

x = 1
y = random (1 to 5)

if (x == y){
  //finished
} else {
  x++
}

This will just add one to x every time until it gets to the same value as y. If, for example, x was 5 it would take five rounds for it to be finished, however if x was 1 it would get it on the first try.

Random:

x = random (1 to 5)
y = random (1 to 5)

if (x == y){
  //finished
} else {
  x = New random (1 to 5)
}

This one will set x to a new number every time. If, for example, x was 5 and y was 5 it may get it on the first try, but in theory it may never get it.

Answer 1

For your sequential search, the expected number of comparisons is the same as the expected value of y, which is 3.

For your random search, the number of comparisons is a geometric random variable (a variable which gives the trial of first success in a series of independent Bernoulli trials) with parameter p = 1/5. The expected value of such a variable is 1/p which in this case is 5.

Since 5 > 3, on average the second approach will involve more comparisons than the first. In practice, the average run time of the second approach will be much worse than this argument suggests since looping through successive integers is fast but random number generation is comparatively slow.

For arbitrary n rather than n = 5, there will be an average of (n+1)/2 comparisons in the first case and n in the second. Random search will thus take on average twice the number of steps. Furthermore, the variance of the number of comparisons required works out to be (n^2-1)/12 (by this) in the first case and n^2-1 in the second, so there is much more variability in the case of random search. If you are an optimist, this implies that you have a higher chance of having significantly less than the expected number, n, of comparisons. But this is balanced out by sometimes needing significantly more. For example, with n=5, there is a (4/5)^10 = 10.7% probability that random search will use more than 10 comparisons.