# Randomized algorithm?

The problem is as follows. Given a set $S$ of natural numbers of size $n$ where each $x_i \in S$ is from the set $[n^2]$. Elements of $S$ are not necessarily pairwise different, i.e., there can be duplicates in $S$. Given an input number $y \in [n^2]$, find the first occurrence of $y$ in $S$, if any. That is, suppose $S$ is an array of numbers, find minimum $i$ such that $x_i = y$, if any.

A naive brute force algorithm would take $O(n)$ time. The question is can we do that in sub-linear time in expectation by, e.g., a Las Vegas algorithm?

-
Without knowing anything else in S, I would guess no. You may as well apply a random permutation to (the indices of) S and then probe the first few entries and hope. Gerhard "Ask Me About System Design" Paseman , 2011.11.14 – Gerhard Paseman Nov 15 '11 at 5:21
When you say "in expectation", what are you averaging over/making random? The algorithm, or $S$? If $S$ is considered random then perhaps something can be done, but if $S$ is fixed and unpleasant.... In the case where the input number is not in $S$, I don't see how you can determine that in fewer than $n$ steps no matter what algorithm you use. - For that matter, I don't see how it helps if $S$ has size $n$ but every element of $S$ is either $0$ or $1$. – Greg Martin Nov 15 '11 at 7:28
"pairwise different" ? – dranxo Nov 15 '11 at 7:49
In expectation means the expected running time because the algorithm should make some random choices. The set $S$ comes in random order, i.e., any one of the $n!$ orderings of elements in $S$ is equally likely. Pairwise different means $\forall (i, j)$ such that $i \neq j$ and $x_i, x_j \in S, x_i \neq x_j$. – VJET Nov 15 '11 at 8:26
It is not clear what your $S$ can have. For example, you say any of the $n!$ orderings is equally likely. But say $S$ has $n$ 1s in it, there is just one ordering, not $n!$? Also, without additional pre-processing, one cannot do much. Could you make your question more precise. – Suvrit Nov 15 '11 at 9:51

## 2 Answers

You can't do that. Most probably $y$ does not occur in $S$ at all, and when it does it will most probably occur only once. In either case you cannot hope to know that fact, or locate $y$, without looking at all elements/half the elements on average.

-

You can certainly construct a data structure such as a hash table, which maps values from $[n^2]$ to indexes in $S$. This will enable a constant-time look-up.

If you are not allowed a pre-computed data structure, then as Marc van Leeuwen pointed out, you can't expect to do better than $O(n)$ time.

-