Expected number of iterations of an exhaustive search

Question

I want to find complexity of the exhaustive search over $M = |X|$ elements which are uniformly distributed to find a particular $x \in X$.

My attempt:

Each element has $\frac{1}{M}$ probability to be my desired value. Finding it in 1st try has a probability $1/M$. Finding it 2nd try has a probability $(1-\frac{1}{M})\times\frac{1}{M}$ and so on.

Hence, I deduce $$ E(\text{# of iterations}) = \sum_{i=1}^Mi(1/M)(1-1/M)^{i-1} $$

Is this correct ? If yes, what does it evaluate to ?

Answer 1

The "uniform" distribution of the $X$'s is not relevant here. You should rather state that the particular $x$ you are looking for is equally likely to be any element of $X$.

Now this particular $x$ is indeed at the $m^{th}$ position with probability $1/M$, and it takes $m$ attempts to find it.

$$E(\#)=\sum_{m=1}^M \frac mM=\frac{M(M+1)}{2M}=\frac{M+1}2.$$

Answer 2

HINT

The probability changes with every round. I.e. that you got the first guess right is indeed $1/M$ but that the second guess is right is already $$\left(1 - \frac{1}{M}\right) \frac{1}{M-1}$$ not $$\left(1 - \frac{1}{M}\right) \frac{1}{M}$$ as you are claiming.

In addition, you likely want to say you want to study the average complexity of your task, since the worst or best complexity would be quite different.