1. ## Expected Value

Can someone help me with this? I'm having a hell of a time with expected value...

Suppose that the probability that a number X is in the first half of a list of N distinct integers is 1/2. And the probability that it is in the second half of the list is 1/4. Find the average number of comparisons used by the linear search algorithm to find X.

2. ## Re: Expected Value

Is this a problem you came up with yourself? The probabilities should add up to one, and the wording is very ambiguous.

Assuming a uniform distribution in the two halves, the expected value is $\sum_{n=1}^{N/2}\frac{1}{N} +\sum_{n=N/2+1}^{N}\frac{1}{2N}$

3. ## Re: Expected Value

No it is a problem from my professor. Could you expand please? Thanks.

4. ## Re: Expected Value

I read it wrong. The probabilities for all events should add up to one, and I forgot that you also have the event where a number is not in the list (with the probability 1/4).

5. ## Re: Expected Value

Could you show me how to solve it?

6. ## Re: Expected Value

It's pretty much a textbook example of the expected value for a discrete stochastic variable.

Let $X$ be the number of comparisons before you find the number you're looking for in a list of N distinct integers.

$P(X=k)=1/N$ if $1 \leq k \leq N/2$
$P(X=k)=1/2N$ if $N/2 < k \leq N$
$P(X=k)=0$ else

The probabilities come from the assumption that the probability mass is distributed in a uniform manner (simply divide the provided probabilities with the number of integers in each half).

7. ## Re: Expected Value

You have three cases:
case 1: found in first half case2:found in second half case3:not found
In each case you should get best case and worst case scenario in order to reach the average case.
case1: best case (found at position 1 --> 1 comparison) worst case (found at position N/2 -->N/2 comparisons)
Average case (1+N/2)/2= (2+N)/4
case2: best case (found at position N/2+1 --> N/2+1 comparisons) worst case (found at position N --> N comparisons)
Average case (N/2+1+N)/2= (3N+2)/2