0
$\begingroup$

I have two search algorithms (for determining if an element $x$ is in a list $A$ of length $n$):

(1) Pick a random index $i$ from $L = [1, \ldots n]$. If $A[i] = x$, terminate. Otherwise, pick a new random index $i$, still in the list $L = [1, \ldots , n]$. Repeat until we've either found a $j$ such that $A[j] = x$ or until every index in $A$ has been exhausted.

(2) Similar to Algorithm $(1)$, except,for element $i$ at every iteration, we perform $L.\text{remove}(i)$ ($L$ has the index $i$ removed from it). This way, we're guaranteed to terminate within $n$ steps (as opposed to potentially running the algorithm forever, as in (1)).

Now, in (1):

If we let $X = $ the number of iterations before Algorithm (1) terminates, we have $$X \sim \text{Geo}(1/n)$$ from which we get $E[X] = 1/(1/n) = n.$

In (2):

Let Y = number of iterations before Algorithm (2) terminates. Let $Y_i$ = event that the algorithm terminates after $i$ iterations.

Then $$P(Y_1) = \frac1n \\ P(Y_2) = \frac{n-1}{n}\left(\frac1{n-1}\right) = \frac1n \\ P(Y_3) = \underbrace{\left(\frac{n-1}n\right)\left(\frac{n-2}{n-1}\right)}_{P(\text{two failures})} \ \underbrace{\left(\frac{1}{n-2}\right)}_{P({\text{one success}})} = \frac1n \\ \vdots \\ P(Y_n) = \frac1n$$

hence $$E[Y] = \sum_{i=1}^n iP(i \ \text{iterations are required to terminate}) = \sum_{i=1}^n \frac1n = n \cdot \frac1n = 1$$ but this doesn't make any sense. How can the expected number of iterations be constant.

Shouldn't $E[Y]$ vary linearly with $n$? What's going on here? Also, when calculating the expected running time (of each of these algorithms), how do I take into account the possibility that the given list does not contain the element $x$? Obviously, it increases the expected running time, but by how much?

$\endgroup$
  • $\begingroup$ What does L.remove(i) do when L is an array? Your second approach doesn't seem easily implementable in the form you listed; if you use an array, you can't efficiently remove, and if you use a linked list, you can't efficiently index into it. $\endgroup$ – D.W. Aug 20 '17 at 2:22
  • $\begingroup$ Where did you get the derivation for (2) from? Are you quoting from somewhere? $\endgroup$ – D.W. Aug 20 '17 at 2:23
1
$\begingroup$

You made a simple algebraic error. You said $\Pr[Y=i] = 1/n$, then you wrote

$$E[Y] = \sum_{i=1}^n i \Pr[Y=i] = \sum_{i=1}^n {1 \over n},$$

but that is incorrect: you omitted the $i$ in the second sum, i.e., you didn't plug in the value of $\Pr[Y=i]$ correctly. Assuming that both indexing into the list and removing an item from the list can be done in one time step, the correct derivation is

$$E[Y] = \sum_{i=1}^n i \Pr[Y=i] = \sum_{i=1}^n i \cdot {1 \over n} = n(n+1)/2 \cdot {1 \over n} = (n+1)/2 = \Theta(n).$$

$\endgroup$
  • $\begingroup$ Hmm, it is easy to remove from an unordered array: L.remove(i) ==> L[i] = L[--L.size] $\endgroup$ – Hari Aug 20 '17 at 3:56
  • $\begingroup$ This constant time deletion essentially means that if your list is unordered, additional randomness isn't useful. You can always apply the replacement algorithm above with i==0 with the constant time deletion. Which, in turn means, you might as well search the list in reverse, which obviouly is \theta{n} $\endgroup$ – Hari Aug 20 '17 at 4:07
  • $\begingroup$ @Hari, you are right. My mistake. Thank you for the correction. $\endgroup$ – D.W. Aug 20 '17 at 6:21
  • $\begingroup$ Damn. Forgot the $i$. Thank you for pointing out this careless mistake! $\endgroup$ – Spongebob Aug 20 '17 at 8:52

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.