Analysis of the synergy of two algorithms in comparison to their simulation in parallel

Question

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.

Answer 1

In Willard's Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time, 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 $\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", which shows that "parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness".