= Solution
The scan permits an arbitrary signed <integer> but prints $\log_2 m$. That expression is undefined for $m\le0$. 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.<Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2014)>[p. 7, Question 5(b), printed logarithm and final absolute-value sentence]{ref}
Choose a fixed positive <integer> $k$ with $1/k\le\epsilon$, and put $B=2^k$. For positive $m$, use <coarse exponential bracketing>: compare against $B,B^2,B^3,\ldots$ 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$. Hence
$$
C(m)\le j+kj+O(1)\le\left(1+\frac1k\right)\log_2 m+k+O(1)\le(1+\epsilon)\log_2 m+O_\epsilon(1).
$$
The additive constant may depend on the fixed $\epsilon$, 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 is
$$
\boxed{C(m)\le(1+\epsilon)\log_2\max(2,|m|)+O_\epsilon(1).}
$$
All 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|$.
Back to article page
