Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 5 / b

The scan permits an arbitrary signed integer but prints ${\log }_{2}m$. That expression is undefined for $m\le 0$. The printed bound is proved below for positive $m$; for the stated signed domain the corresponding bound uses ${\log }_2\max (2,|m|)$. This is a source qualification, rather than an unreadable part of the question.^[ref]

Choose a fixed positive integer $k$ with $1/k\le ϵ$, and put $B=2^k$. For positive $m$, use coarse exponential bracketing: compare against $B,B^2,B^3,\dots$ until the first $B^j\ge m$. Equality determines $m$ immediately. Otherwise, $B^{j-1}<m<B^j$, except in the first interval where the lower bound is zero. Apply binary search to the remaining integer candidates.

There are at most $j$ bracketing comparisons and at most $kj+O(1)$ subsequent comparisons, because the interval width is at most $B^j=2^{kj}$. Minimality of $j$ gives $j\le ({\log }_{2}m)/k+1$. HenceThe additive constant may depend on the fixed $ϵ$, but is independent of $m$. Taking larger jumps in the bracketing phase reduces its leading comparison cost; the overshoot costs only the fixed number $k$ of extra binary search levels.

For signed inputs, first compare with zero. If negative, set $u=|m|$ conceptually and perform the same search for $u$: comparing $m$ with $-t$ yields the reversed outcome of comparing $u$ with $t$. Thus every test is still a permitted test of the sign of $m-x$. Return zero immediately on equality in the initial test. The corrected all-input bound isAll thresholds are exact integers, generated by repeated multiplication by $B$. Their arithmetic and storage costs are outside the requested comparison model; bounded machine arithmetic would not suffice for arbitrarily large $|m|$.