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?

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Nov 15 '11 at 5:21
  • $\begingroup$ 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$. $\endgroup$ – Greg Martin Nov 15 '11 at 7:28
  • 1
    $\begingroup$ "pairwise different" ? $\endgroup$ – dranxo Nov 15 '11 at 7:49
  • $\begingroup$ 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$. $\endgroup$ – Joe Nov 15 '11 at 8:26
  • $\begingroup$ 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. $\endgroup$ – Suvrit Nov 15 '11 at 9:51

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.


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.