Find the average number of comparisons to search for a target element x using the sequential search algorithm under the assumption that x is not in the list 80% of the time, but if x is in the list it is equally likely to be at any of the n positions.

Question

Bradyn Braun

Mathematics

23 June, 00:43

Find the average number of comparisons to search for a target element x using the sequential search algorithm under the assumption that x is not in the list 80% of the time, but if x is in the list it is equally likely to be at any of the n positions.

+5

Answers (1)

Know the Answer?

Jon Frazier · Answer 1

0.9n + 0.1, with n the length of the list.

Step-by-step explanation:

Lets denote with n the length of the list.

80% of the time x is not in the list, so 80% of the time we make n comparisons (or we make n comparisons with probability 0.8).

20% of the time (probability 0.2) we use linear search to find x, since x is equally likely to be at any place on the list, then we should expect that, provivded that x is in the list, we should make (1+2+3+4 + ... + n) / n comparisons (on average). Using Gauss's sum we conclude that the number is equal to (n+1) * n / (2n) = (n+1) / 2 (here we are assuming that x appears only once on the list).

As a conclussion, the average number of comparisons we make is

0.8*n + 0.2 * (n+1) / 2 = 0.8n + 0.1n + 0.1 = 0.9n + 0.1

I hope that works for you!