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