Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
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)$.
