0
$\begingroup$

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 $

$\endgroup$
6
  • $\begingroup$ Do I correctly understand, that last summand is for the case when we did not find the required $x$? $\endgroup$ – zkutch Dec 1 '20 at 16:55
  • $\begingroup$ Yes.it for we did not find the required x $\endgroup$ – user128010 Dec 1 '20 at 17:37
  • $\begingroup$ 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. $\endgroup$ – Steven Dec 1 '20 at 18:41
  • $\begingroup$ According to this comment what we do? $\endgroup$ – user128010 Dec 1 '20 at 20:04
  • 2
    $\begingroup$ 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$ $\endgroup$ – Steven Dec 1 '20 at 20:16

Your Answer

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