= Solution
On a worst-case branch, the described sequential quarter-point tests make three equality tests per reduction, giving $Q(n)=Q(n/4)+3$ until constant size. Thus $Q(4^k)=3k+O(1)$. Ordinary <binary search> makes one equality test per halving: $B(n)=B(n/2)+1$, so $B(4^k)=2k+O(1)$.
\b[Both searches take $\Theta(\log n)$ time, but the specified quaternary search uses asymptotically $3/2$ as many equality tests.] A quarter-sized branch does not compensate for the three sequential pivots. The numerical ratio concerns precisely the unit equality-test model in the paper; counting ordering comparisons, array accesses or a differently arranged pivot decision tree requires its own constants.
Back to article page
