1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – lulu
    Mar 4, 2017 at 0:42
  • $\begingroup$ @lulu, Looks like typo and it should be $p_n = \frac13$. $\endgroup$
    – Smylic
    Mar 4, 2017 at 21:15

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.