1
$\begingroup$

Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime?

My thoughts so far:

The chance to find the element is $\frac{1}{n}$ in every step. Thus, to find the element after $k$ steps is $(\frac{1}{n})^k$. Now we can calculate the expected value and get $\frac{n}{(n-1)^2}$. But: that doesn't really make as it returns results $< 1$ for $n > 2$.

$\endgroup$
1
$\begingroup$

The probability you find the element in each guess is $1/n$. The number of guesses until you find it is a geometric random variable with success probability $1/n$, whose expectation is $n$.

Your formula is wrong – the probability to find the element after $k$ steps is $(1-1/n)^{k-1} (1/n)$.

$\endgroup$
  • $\begingroup$ After giving it some more thought, using the geometric distribution makes perfectly sense. Thanks! $\endgroup$ – msiemens Nov 1 '14 at 20:11

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.