Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 5 / b / 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)$.

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.