View Full Version : Probability of algorithm? (comparing strings read from file)

04-05-2008, 10:50 PM

A string is like a list of words such as kite, bake, hat, etc. I am reading 100 strings (words) from a file. Then I am chosing a random string from the file and counting the number of comparisons for the random string using sequential search. This operation is performed 1000 times and finally after 1000 times I am finding the average number of comparisons. So in this case, the probability that a string will exist is equally likely to be at any of the n positions. Therefore, the average comparisons would be (n+1)/2 given that n = 100 so (100+1)/2 = 50.5

I am told to assume that the probability of a string (word) is not in the list is 0.2. Then I am asked to compute the average number of comparisons required doing the process I have described in the previous paragraph. This is the part in which I do not understand quite clearly.

Any help is appreciated!

04-08-2008, 10:40 AM
Pr(In the List)*(Average Comparisons to determine that) + Pr(NOT in the list)*(Average Comparisons to determine that)

Total Average Comparison Cycles
0.80(50.5) + 0.20(100)