0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ This is just the geometric distribution with probability $\frac{1}{d}$, you can look it up online. Your method is completely fine as well. $\endgroup$
    – Sawarnik
    May 25 at 20:19
1
$\begingroup$

The right way to prove this is to use the notion of expected value.

Given an array $[x_1, …, x_n]$, an index $1\leqslant k \leqslant n$ and a value searched $1\leqslant i \leqslant d$, the probability that $x_k = i$ is $\frac{1}{d}$.

Now what we want to calculate is the expected value of the first index $k$ such that $x_k = i$. For that, we need to know the probability, for each index $k$, that $x_k$ is the first value equal to $i$. This probability is $p_k = \frac{1}{d}\left(1-\frac{1}{d}\right)^{k-1}$ (meaning that we did not encounter $i$ within indices $1…k-1$ but in index $k$).

The expected value is then $\sum\limits_{k=1}^{n}kp_k = \frac{1}{d}\sum\limits_{k=1}^nk\left(\frac{d-1}{d}\right)^{k-1}\leq \frac{1}{d}\sum\limits_{k=1}^{\infty}k\left(\frac{d-1}{d}\right)^{k-1}$.

We can show that this last quantity is equal to $\frac{1}{d}\frac{1}{\left(\frac{1}{d}\right)^2} = d$.

This indeed means that the average time complexity is $O(d)$.

$\endgroup$
3
  • $\begingroup$ This indeed proves my point, but how is it the "right" way? Is my proof malformed? BTW it seems that the proof that your infinite sum converges can be done using a "recursion trick" similar to mine, e.g. here : youtube.com/watch?v=Ch9uCBm-kUE $\endgroup$
    – scand1sk
    May 25 at 14:34
  • 1
    $\begingroup$ I am not familiar with your way to find a recursion formula for the expected value so I cannot really confirm or deny your proof. However, the infinite sum has indeed many ways to be calculated, so it is not surprising to find a "recursion trick" for it. $\endgroup$
    – Nathaniel
    May 25 at 14:38
  • 2
    $\begingroup$ @scand1sk Your proof is fine. To make it completely formal you would use conditionnal expectations but it boils down to exactly your argument. $\endgroup$
    – Tassle
    May 25 at 21:02

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.