Average Case runtime for random choice search 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 $&lt; 1$ for $n &gt; 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)$.