<p>In Willard's <a href="http://dx.doi.org/10.1137/0214071" rel="nofollow">Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time</a>, he references a preliminary version (of the linked paper) entitled "Surprisingly efficient search algorithms for nonuniformly generated files" appearing at the 21st Allerton Conference on Communication Control and Computing in 1983, pp. 656-662. I can't find this paper on the web, but in the later (linked) version above, he says that the older paper shows that the synergy between binary and interpolation search can reduce search time to $o(\log n)$ for certain non-uniform distributions of record keys.</p>

<p>Specifically, call a <a href="http://en.wikipedia.org/wiki/Probability_density_function" rel="nofollow">PDF</a> $\mu$ regular if there are $b_1, b_2, b_3, b_4$ such that $\mu(x) = 0$ for $x &lt; b_1$ or $x &gt; b_2$ and $\mu(x) \geq b_3 &gt; 0$ and $|\mu\prime(x)| &lt; b_4$ for $b_1 \leq x \leq b_2$. For data produced by regular PDFs, interpolation search takes $\Omega(\log n)$ expected time, while binary search takes $\Theta(\log n)$ expected time. Interleaving them, however, takes $O(\sqrt{\log n})$ expected time.</p>

<p>You may also be interested in Willard and Reif's <a href="http://www.cs.duke.edu/~reif/paper/willard/interpsearch.pdf" rel="nofollow">"Parallel processing can be harmful: The unusual behavior of interpolation search"</a>, which shows that "parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness".</p>

CC BY-SA 2.5
2011-03-23T05:52:48.703Z
I tried to get the paper from the Allerton Conference, but I can't even find it in a library, except at ETH-Bibliothek Zurich, which is very far from where I live. I emailed the author, but I have yet to hear back. Please let me know if you find the paper anywhere.
jbapple
CC BY-SA 2.5
2011-02-25T15:19:10.873Z
Thanks! Exactly the type of results that I was expecting to have been done. I will try to download the papers from the university.
J.y B.y
CC BY-SA 2.5
2011-02-22T05:11:39.213Z
2011-02-22T06:38:41.950Z
2011-02-22T06:38:41.950Z
jbapple
<p>Consider the following two algorithms for searching in a sorted array of $n$ elements: </p>

<p>A) interpolation search and binary search simulated in parallel, and </p>

<p>B) search through alternating interpolation steps and binary steps. </p>

<p>Both algorithms are of worst case complexity $2\lg n+1$ (and average complexity $2\lg\lg n$ for a reasonable distribution). Is there a complexity model which permits to separate those two algorithm (expressing when one is better than the other)? In particular, is there an example where the simulation in parallel is outperforming the mixed search algorithm?</p>

<p>---Some Basic Background---</p>

<p>1) Interpolation for element $x$ in a sorted array $T$ between position $i$ and $j$ makes a comparison at position $g=i+(j-i)/(T[j]-T[i])*(x-T[i])$, and reduces the search interval to $[i,g]$ or $]g,j]$ according to the result (as opposed to binary search, which compares $x$ to the element at position $(i+j)/2$.)</p>

<p>2) The worst case complexity of the search algorithm simulating in parallel binary search and interpolation search is $2\lg n+1$: Given two algorithms $A$ and $B$ of worst case complexities $f(n)$ and $g(n)$, the worst case of the parallel simulation of $A$ and $B$, stopping as soon as one terminates, has complexity $2\min\{f(n),g(n)\}\in O(\min{f(n),g(n)})$. The complexity of the search alternating steps from binary search and interpolation search is $2\lg n+1$ as well, because the search interval is at least reduced by two every two comparison.</p>

CC BY-SA 2.5
2010-10-15T05:45:38.283Z
How does interpolation search work ?
Suresh Venkat
CC BY-SA 2.5
2010-10-15T10:55:20.523Z
@Suresh The idea is to estimate the next position to be checked in a sorted array based on a linear interpolation of the search key and the extremal values of the search interval.
Sylvain Peyronnet
CC BY-SA 2.5
2010-10-15T16:47:39.333Z
in that case I'm a little surprised that interpolation search has a worst-case $\log n$ bound. I thought it would be worse
Suresh Venkat
CC BY-SA 2.5
2010-10-15T19:21:28.977Z
You're right, the one I know has worst case O(n) and average case log(log(n)). Jeremy, is this a specific interpolation search ?
Sylvain Peyronnet
CC BY-SA 2.5
2010-10-15T20:36:45.580Z
If I am not mistaken, the point of running two different algorithms in parallel (or interleaving two algorithms) is that the worst-case time becomes the _faster_ of the worst-case times of the two algorithms.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-16T02:32:07.117Z
@Tsuyoshi, you're correct. I think the question is (really) asking about non-worst-case analysis -- for example, average case runtime or expected runtime over certain distributions over the search keys. Basically, any type of "finer grade" analysis than optimizing only for the worst case.
Daniel Apon
CC BY-SA 2.5
2010-10-16T12:16:18.267Z
I do not think I understand the question, and I guess the reason is related to Daniel’s comment.  In what sense does the second algorithm (alternating interpolation steps and binary steps) perform much better?
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-16T23:04:50.477Z
I think the question could really benefit from a concrete, specific example of the claim "The second one will perform much better on some examples, because of the synergy between the two algorithms."
Daniel Apon
CC BY-SA 2.5
2010-10-17T21:26:59.210Z
Voted to close.  As I wrote in a comment, I cannot understand the question in its current form, and I believe that it is not my fault.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-23T03:17:05.550Z
Now that the question has been edited, I think it makes more sense and should not be closed.
jbapple
<ds.algorithms><time-complexity>
Analysis of the synergy of two algorithms in comparison to their simulation in parallel
J.y B.y
# Analysis of the synergy of two algorithms in comparison to their simulation in parallel

(Asked by: username_0 on 2010-10-15)

Consider the following two algorithms for searching in a sorted array of $n$ elements:

A) interpolation search and binary search simulated in parallel, and

B) search through alternating interpolation steps and binary steps.

Both algorithms are of worst case complexity $2\lg n+1$ (and average complexity $2\lg\lg n$ for a reasonable distribution). Is there a complexity model which permits to separate those two algorithm (expressing when one is better than the other)? In particular, is there an example where the simulation in parallel is outperforming the mixed search algorithm?

---Some Basic Background---

1) Interpolation for element $x$ in a sorted array $T$ between position $i$ and $j$ makes a comparison at position $g=i+(j-i)/(T[j]-T[i])\*(x-T[i])$, and reduces the search interval to $[i,g]$ or $]g,j]$ according to the result (as opposed to binary search, which compares $x$ to the element at position $(i+j)/2$.)

2) The worst case complexity of the search algorithm simulating in parallel binary search and interpolation search is $2\lg n+1$: Given two algorithms $A$ and $B$ of worst case complexities $f(n)$ and $g(n)$, the worst case of the parallel simulation of $A$ and $B$, stopping as soon as one terminates, has complexity $2\min\{f(n),g(n)\}\in O(\min{f(n),g(n)})$. The complexity of the search alternating steps from binary search and interpolation search is $2\lg n+1$ as well, because the search interval is at least reduced by two every two comparison.

**Tags:** ds.algorithms, time-complexity

> **Comments:**
> **username_1**: How does interpolation search work ?  
> **username_2**: @Suresh The idea is to estimate the next position to be checked in a sorted array based on a linear interpolation of the search key and the extremal values of the search interval.  
> **username_1**: in that case I'm a little surprised that interpolation search has a worst-case $\log n$ bound. I thought it would be worse  
> **username_2**: You're right, the one I know has worst case O(n) and average case log(log(n)). Jeremy, is this a specific interpolation search ?  
> **username_3**: If I am not mistaken, the point of running two different algorithms in parallel (or interleaving two algorithms) is that the worst-case time becomes the _faster_ of the worst-case times of the two algorithms.  
> **username_4**: @Tsuyoshi, you're correct. I think the question is (really) asking about non-worst-case analysis -- for example, average case runtime or expected runtime over certain distributions over the search keys. Basically, any type of "finer grade" analysis than optimizing only for the worst case.  
> **username_3**: I do not think I understand the question, and I guess the reason is related to Daniel’s comment.  In what sense does the second algorithm (alternating interpolation steps and binary steps) perform much better?  
> **username_4**: I think the question could really benefit from a concrete, specific example of the claim "The second one will perform much better on some examples, because of the synergy between the two algorithms."  
> **username_3**: Voted to close.  As I wrote in a comment, I cannot understand the question in its current form, and I believe that it is not my fault.  
> **username_5**: Now that the question has been edited, I think it makes more sense and should not be closed.  

---

## 1 answers

### Answer by username_5 on 2011-02-22. Score: 4 | Accepted answer

In Willard's [Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time](http://dx.doi.org/10.1137/0214071), he references a preliminary version (of the linked paper) entitled "Surprisingly efficient search algorithms for nonuniformly generated files" appearing at the 21st Allerton Conference on Communication Control and Computing in 1983, pp. 656-662. I can't find this paper on the web, but in the later (linked) version above, he says that the older paper shows that the synergy between binary and interpolation search can reduce search time to $o(\log n)$ for certain non-uniform distributions of record keys.

Specifically, call a [PDF](http://en.wikipedia.org/wiki/Probability_density_function) $\mu$ regular if there are $b\_1, b\_2, b\_3, b\_4$ such that $\mu(x) = 0$ for $x < b\_1$ or $x > b\_2$ and $\mu(x) \geq b\_3 > 0$ and $|\mu\prime(x)| < b\_4$ for $b\_1 \leq x \leq b\_2$. For data produced by regular PDFs, interpolation search takes $\Omega(\log n)$ expected time, while binary search takes $\Theta(\log n)$ expected time. Interleaving them, however, takes $O(\sqrt{\log n})$ expected time.

You may also be interested in Willard and Reif's ["Parallel processing can be harmful: The unusual behavior of interpolation search"](http://www.cs.duke.edu/~reif/paper/willard/interpsearch.pdf), which shows that "parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness".

> **Comments:**
> **username_0**: Thanks! Exactly the type of results that I was expecting to have been done. I will try to download the papers from the university.  
> **username_5**: I tried to get the paper from the Allerton Conference, but I can't even find it in a library, except at ETH-Bibliothek Zurich, which is very far from where I live. I emailed the author, but I have yet to hear back. Please let me know if you find the paper anywhere.  

---

