# answers Average case analysis of linear search

Suppose we have an array$$[1..n]$$ and run linear search to find $$x$$, on it with following specification: probability of existence $$x$$ in first half of array is $$p$$,and probability of existence $$x$$ in second half is $$3p$$ and in each half probability of any element to be x is equally likely.Calculate Average case linear search. Is my answer true?

$$E[successful]+unsuccessful=\sum_{i=1}^{n/2}pi + \sum_{i=\frac{n}{2}+1}^{n}3pi + (1-p)(1-3p)n$$

• Do I correctly understand, that last summand is for the case when we did not find the required $x$? – zkutch Dec 1 '20 at 16:55
• Yes.it for we did not find the required x – user128010 Dec 1 '20 at 17:37
• The events "the element is not in the first half" and "the element is not in the second half" are not independent, you can't just multiply their probabilities. – Steven Dec 1 '20 at 18:41
• According to this comment what we do? – user128010 Dec 1 '20 at 20:04
• The event $F$ "an element is not found is" is the complement of the event "an element is found" which is the union of the events $A$ "an element is found in the first half" and $B$ "an element is found in the second half". Since $A$ and $B$ are mutually exclusive, the probability of $A \cup B$ is $\Pr(A)+P(B)=p+3p=4p$, hence $\Pr(F) =1-P(A \cup B) =1-4p$ – Steven Dec 1 '20 at 20:16