Thread: 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.

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

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

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

Could you show me how to solve it?

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

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

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

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
case 3 (Not found --> N comparisons)
Finally the average number of comparisons is : 1/2 *((N+2)/4) + 1/4 * ((3N+2)/2) + 1/4 * N