= Coarse exponential bracketing
{title2=$C(m)\le(1+1/k)\log_2 m+O_k(1)$}
To discover a positive unknown <integer> $m$ by comparisons, test the thresholds $2^k,2^{2k},\ldots$ for fixed $k\ge1$. If the first threshold not smaller than $m$ has index $j$, fewer than $2^{kj}$ candidates remain and <binary search> needs at most $kj+O(1)$ comparisons. Since $j\le\log_2(m)/k+1$, the total is at most $(1+1/k)\log_2 m+O_k(1)$. Choosing $k\ge1/\epsilon$ makes the leading constant at most $1+\epsilon$; the additive constant may depend on $\epsilon$.
Back to article page
