Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
"pairwise different" ? –  rcompton 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
show 4 more comments

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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