1
$\begingroup$

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?

$\endgroup$
9
  • $\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$ Nov 15, 2011 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$ Nov 15, 2011 at 7:28
  • 1
    $\begingroup$ "pairwise different" ? $\endgroup$
    – dranxo
    Nov 15, 2011 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, 2011 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, 2011 at 9:51

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.