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?

Improve this question
$\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$
    – Gerhard Paseman
    Commented 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$
    – Greg Martin
    Commented Nov 15, 2011 at 7:28
  • 1
    $\begingroup$ "pairwise different" ? $\endgroup$
    – dranxo
    Commented 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
    Commented 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
    Commented Nov 15, 2011 at 9:51

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .