Probabilistic search - psearch.tar.gz

[kwilson at nowhere.com]

Hi there Sandresh,

The "bug" within your program is simply that your base case (or terminating
case) for the recursion is (size == 1) and you increment/decrement a variable
(ie. depth)  outside of this base case "if" statement. 

This leads to a recursively maximized value of 9 (or log base 2 of 512), as
pointed out. Then, since no variable is updated in the base case "if" statement,
you don't actually add to the comparison total accordingly. Thus you mistakenly
get a maximal depth of 9 for each search. This is not actually the depth to find
the element you are searching for, but rather the depth to the "size == 1" base
case.

Now you will say that "this is not true" since the base case is reached many
times during the search process before the search is terminated....not just once
after depth equals nine. The static "depth" variable is not being updated
properly, though.

Once you try the changes suggested below you will see that the "Average depth"
of the 2048 searches per distribution will be approximately 256. Single "depths"
or comparisons will range from 1 to 512 as would be expected. The average per
distribution is approximately N/2 as several others in this thread have pointed
out, as the correct average case search for an element in a randomized array of
size N. If you want to argue that the "depth" of the actual comparisons never
exceeds 9, then that is obviously true because log base 2 of 512 is 9.....but
that doesn't mean that the number of comparisons is 9. Sorry ;)

Hope the code change and viewing the results will clear things up if anyone
can't follow my explanation above (my fault for not explaining things well
enough, I'm afraid).


Try these simple changes:

in psearch.c 

on line 9:
add ------>  ++comparisons;


on line 18:
comment out --------> //comparisons = ++depth;


on line 31:
comment out --------> //--depth;

Thanks,
K.Wilson