# time complexity – 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.
$$E(successful)+unsuccessful=sum_{i=1}^{n/2}pi + sum_{i=frac{n}{2}+1}^{n}3pi + (1-p)(1-3p)n$$