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