1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – A.S. Jan 27 '16 at 20:36
  • $\begingroup$ $P(L[i]=x)=0.75$ should be $P(\exists i: L[i]=x)=0.75$ , no? $\endgroup$ – leonbloy Jan 27 '16 at 20:41
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "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) $\endgroup$ – leonbloy Jan 27 '16 at 20:41
  • $\begingroup$ I inserted an assumption of distinctness. $\endgroup$ – André Nicolas Jan 27 '16 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.