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.

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!

4

step-by-step explanation: