# Finding the expected value of searching an array. if there are different probabilities for each position?

The probability of finding an item in the first position in an array is 1⁄2, the probability of finding it in the last is 1/3

The item we're searching for is definitely in the array.

If the item is in the $n_{th}$ position then it takes n operations to find the item.

My attempt finding the expected value of the amount of time it takes on average to find the item:

(1)

$p_1 = \frac{1}{2}, p_n = \frac{n}{3} , p_i = \frac{1}{6(n-2)}, 1 < i < n$

(2)

$E(n) = \frac{1}{2} + \frac{n}{3} + \frac{1}{6(n-2)} (\sum_{i=1}^{n-1} - 1)$

(3)

$E(n) = \frac{1}{2} + \frac{n}{3} + \frac{1}{6(n-2)} \frac{(n-1)n-2}{2}$

(4)

$E(n) = \frac{1}{2} + \frac{n}{3} + \frac{(n^2 - n) - 2}{12(n-2)}$

However it seems like this is $\in O(n^2)$ Which doesn't make sense as in the worst case it takes O(n) to find the item. Where did I go wrong?

• Not sure this is clear. If $n≥2$ then $p_1+p_n≥ \frac 12 +\frac 23 >1$....so might the item be in more than one place? Or is $p_i$ not meant to be a probability?
– lulu
Mar 4, 2017 at 0:42
• @lulu, Looks like typo and it should be $p_n = \frac13$. Mar 4, 2017 at 21:15

Don't worry, any function from $O(n)$ belongs to $O(n^2)$. Anyway if you reduce the last fraction, you'll get: $$E(n) = \frac12 + \frac n3 + \frac{n - 1}{12} = O(n).$$