0
$\begingroup$

Let $S$ be an array of length $n$ containing a random permutation of numbers from $0$ to $n-1$. What is the most efficient (in expectation) algorithm for finding the location of a given number $k$ in $S$? In other words, finding index $i$, such that $S[i]=k$.


I watched a video about a related puzzle and it seems that in expectation we can do better than a linear search. The idea is to search $S[k]$ then $S[S[k]]$ then $S[S[S[k]]]$ and so on. I think this will find the required index faster than checking every element (on average), but I am not sure.

I wrote some Java code to simulate this algorithm and here are the results for $n=3$. I show every possible permutation and the number of steps required to find every possible $k$. Each element of the permutation is written in the form "index:value".

0:0 1:1 2:2
0 found in 1 steps
1 found in 1 steps
2 found in 1 steps
maximum steps for this permutation 1

0:0 1:2 2:1
0 found in 1 steps
1 found in 2 steps
2 found in 2 steps
maximum steps for this permutation 2

0:1 1:0 2:2
0 found in 2 steps
1 found in 2 steps
2 found in 1 steps
maximum steps for this permutation 2

0:1 1:2 2:0
0 found in 3 steps
1 found in 3 steps
2 found in 3 steps
maximum steps for this permutation 3

0:2 1:0 2:1
0 found in 3 steps
1 found in 3 steps
2 found in 3 steps
maximum steps for this permutation 3

0:2 1:1 2:0
0 found in 2 steps
1 found in 1 steps
2 found in 2 steps
maximum steps for this permutation 2

average of maximum steps for all permutations 2.1666666666666665

This algorithm has an average for all permutations of 2.17 steps. Meanwhile the linear algorithm of checking every element will always have an element that requires the maximum steps of 3, so its average over all permutations will be 3, which is worse.

As $n$ increases the number of steps required by the above algorithm seems to approach $2n/3$.

But can we do better?

$\endgroup$
17
  • $\begingroup$ No very elegant to silently modify the question. By the way, this order makes no difference. $\endgroup$ Jul 16 at 9:22
  • $\begingroup$ Sorry I didn't change the question itself. I only added an idea for a solution. I am not sure if its optimal or what it's complexity is. $\endgroup$ Jul 16 at 9:29
  • $\begingroup$ Also not elegant to disregard my answer. $\endgroup$ Jul 16 at 9:31
  • $\begingroup$ Your answer may be optimal after all. I am just not sure yet. $\endgroup$ Jul 16 at 9:36
  • 1
    $\begingroup$ By the way, the average of the maximum times is not the average time. $\endgroup$ Jul 18 at 7:58

2 Answers 2

4
$\begingroup$

Linear search.

Reading values from $S$ give you no information on where $k$ can be and you can't avoid exhaustive search. If the permutations are equiprobable, whatever the order in which you try the locations, the distribution of the number of trials is uniform. The expectation of the number of comparisons is $\dfrac{n-1}2$ (best case $1$, worst $n-1$).

Note that knowing the particular values (naturals $1$ to $n$) helps in no way.


Update:

The correct value of the expectation is

$$\frac{n^2+n-2}{2n},$$ my bad.

$\endgroup$
0
$\begingroup$

Lets take a smaller example. Consider you have $10$ positions $[0, 1, 2, ..9]$ and the numbers are distributed as position $i$ has the number $(i + 1)mod10$. Now pick any $k$, it's easy to see that you'll have to traverse all the positions. So asymptotically, you have no benefit.

As far as expectation is concerned @Yves Daoust's answer gives you why it's unaffected. Also, implementing such a strategy in code isn't particularly helpful, it will only obfuscate the code, may make it harder for the compiler to optimize and may invalidate cache benefits if you are dealing with extremely large arrays.

$\endgroup$
9
  • $\begingroup$ In this particular case yes you would need to traverse all the positions. However, for a random permutation you would need to traverse fewer positions. $\endgroup$ Jul 16 at 11:40
  • $\begingroup$ Even linear search would need to traverse fewer positions for "some random permutation" :) $\endgroup$
    – Rinkesh P
    Jul 16 at 12:15
  • $\begingroup$ @DmitryKamenetsky: " you would need to traverse fewer positions": how do you justify this claim ? (By the way, you seem ignorant of the fact that in most cases the iteration $i=S[i]$ will loop and fail to find $k$.) $\endgroup$ Jul 17 at 17:27
  • $\begingroup$ @YvesDaoust I've added an explanation in the question. I hope that helps? $\endgroup$ Jul 18 at 0:54
  • $\begingroup$ @DmitryKamenetsky: still quite insufficient. There is no analysis of the reason, and a mere "seems to". $\endgroup$ Jul 18 at 7:53

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.