Question

How many comparisons (both successful and unsuccessful) will be made by the brute-force algorithm in searching for each of the following patterns in the binary text of one thousand zeros?

a.00001     b.10000     c.01010

Answer 1

Here is the answer for your question....

a)00001

Answer:- There are total 4980 comparisons will occur,including both successful and unsuccessful comparisons.

   Given Search Pattern 00001 is of length 5. so there will be 1000 -5 + 1 = 996 iterations will occur. In that , the first 4 comparisons would be successful and the last comparison will be unsuccessful. so 996*4 = 3,984 will be consider as successful comparisons and rest 996*1 = 996 will be treated as unsuccessful comparisons. hence Total comparisons are = 3984 + 96 = 4980

b)10000

Answer:- There are total 996 comparisons will occur,including both successful and unsuccessful comparisons.

we already know that there are 996 iterations. In that, the first comparison would itself be unsuccessful. so there is no successful comparison.only we have 996*1 = 996 unsuccessful comparisons.Hence Total comparisons are = 996.

c)01010

Answer:- There are total 1992 comparisons will occur,including bot successful and unsuccessful comparisons.

we already know that there are 996 iterations. In that, the first comparison would be successful and the second comparison would be unsuccessful. so there are 996*1 = 996 successful comparisons and rest will be 996*1 = 996 unsuccessful comparisons. hence total comparisons are 1992.