# Randomized linear search -- Why does reducing the sample size make the running time constant?

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?

• 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.
– D.W.
Aug 20, 2017 at 2:22
• Where did you get the derivation for (2) from? Are you quoting from somewhere?
– D.W.
Aug 20, 2017 at 2:23

## 1 Answer

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

• Hmm, it is easy to remove from an unordered array: L.remove(i) ==> L[i] = L[--L.size]
– Hari
Aug 20, 2017 at 3:56
• 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}
– Hari
Aug 20, 2017 at 4:07
• @Hari, you are right. My mistake. Thank you for the correction.
– D.W.
Aug 20, 2017 at 6:21
• Damn. Forgot the $i$. Thank you for pointing out this careless mistake! Aug 20, 2017 at 8:52