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

Question

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?

Answer 1

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)$.