It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear). I have read several proofs, usually assuming either:
- that $i$ and the elements of $L$ take values in an infinite domain, in which case the probability of $i$ being is $L$ tends towards 0 and the algorithm will iterate over all elements.
- that $i$ is present exactly once in $L$, in which case the expectancy on the number of iterations is $(1 + 2 + … + n)/n \in O(n)$.
However, I would like to introduce the case where $i$ and the elements of $L$ take values in a finite domain of size $d$. Is this case studied somewhere? I have failed to find proof online, but I have found one that finds that the complexity is $O(d)$, and would like to know whether it is correct. I assume that each element of $L$ is a random value from $[1..d]$. I want the expectancy $E$ on the number of iterations of the linear search algorithm. I also assume that $L$ has infinite size, without loss of generality, I do not want to question the fact that linear search is $O(n)$ on average, it clearly is. My point is that linear search is both $O(n)$ AND $O(d)$. I have interest in the case where $d \ll n$.
At the first iteration, there is a $1/d$ probability that the sought element is found and the algorithm stops. In other cases, i.e. with a probability of $(d-1)/d$, the algorithm iterates. Recursively, I have $E = 1 + E\cdot(d-1)/d$, which boils down to $E=d$.
Also, this seems related to the fact that $\sum_{n=0}^{\infty} \frac{n}{e^n} \in O(1)$, if the recursion is unrolled. My proof, however, seems almost too easy. Is there a fail somewhere?