# Average case of element comparisons when searching for an element x with a specific probability

I just had a midterm, and unfortunately our professor has stated that he will neither discuss nor post any solutions to the midterm, so I'm posting a question that was on it here in hopes that someone can help me.

The question was as follows:

We have a sequential search algorithm that runs over a list $L$, and looks for $x$ when the number of elements $n = 25$. The probability that $x$ is in the list $P(L[i] = x) = 0.75$. The probability that $x$ is not in the list, $P(L[i] \neq x) = 0.25$

1. What is the average case of element comparisons when searching for an element $x$ that is not in the list, when $n = 25$?

2. What is the average case of element comparisons when $x$ is in the list and $n = 25$?

3. What is the average case of element comparisons when $n = 25$?

Here is my attempt at solving this:

1. For this problem, I figured since x will never be in the list, it would just be $n - 1$ comparisons on average, every time, therefore we would have $25 - 1 = 24$ comparisons on average. I realize I am not factoring in any probability and so this might be wrong.. but it made sense at the time.

2. The average case of element comparisons is $(P(x \text{ in list}) \times \frac{n-1}{2}) + (P(x \text{ not in list}) \times \frac{n-1}{2})$ This is $(0.25 \times \frac{24}{2}) + (0.75 \times \frac{24}{2}) = 3 + 9 = 12$ comparisons on average. Now I have no idea if this is the correct thing to be doing, to be honest I just guessed because I vaguely remembered hearing that the average should be the probability times the target value.

3. For this one since we don't know if $x$ is in the list or not, I just guessed $24$. I'm not very smart.

Could anyone help me make sense of this, or help me understand these average formulas / problems better?

• If the element is not in the list, you'll have $n$ comparisons always and hence on average. If the element is in the list, you'll have average of $\frac {n+1}2$ comparisons. Sum these with weights $0.25$ and $0.75$ respectively. – A.S. Jan 27 '16 at 20:36
• $P(L[i]=x)=0.75$ should be $P(\exists i: L[i]=x)=0.75$ , no? – leonbloy Jan 27 '16 at 20:41

## 1 Answer

If $x$ is not in the list, we will use $25$ comparisons.

For $x$ in the list, we assume the elements in the list are distinct. We also assume, not necessarily reasonably, that $x$ is equally likely to be the first element, the second, and so on. So the average number of comparisons is $\frac{1}{25}(1+2+\cdots+25)$, which simplifies to $13$.

The average number of comparisons in general is therefore $(0.25)(25)+(0.75)(13)$.

• "we will assume, not necessarily reasonably, that it is equally likely to be the first element..." This assumes, also, that the element will be on the list in a single position (which is probably right) – leonbloy Jan 27 '16 at 20:41
• I inserted an assumption of distinctness. – André Nicolas Jan 27 '16 at 20:43