0
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\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.