Past exam of the probability, statistics and options I course of the University of Oxford / 2011 / U / 1 / a

The bisection method begins with a finite interval $[a,b]$ on which the continuous function has opposite signs at its endpoints. The intermediate value theorem guarantees a root inside. Evaluate at the midpoint $m=(a+b)/2$. If $f(m)=0$, stop. Otherwise retain the half whose endpoints have opposite signs and repeat. An endpoint that is already a root is returned immediately. The nested intervals retain a root and their lengths halve, so their midpoints converge to a root.

If the starting length is $L=b-a$, then after $k$ interval halvings the current midpoint is at most $L/2^{k+1}$ from some root remaining in the bracket. Thus, with the midpoint returned after those halvings, it suffices to takeIf iterations instead count midpoint evaluations starting with the initial midpoint as evaluation one, the usual bound is $n\ge \lceil {\log }_2(L/ϵ)\rceil$, with at least one evaluation unless an endpoint root has already been found. Stating the counting convention avoids an apparent one-step discrepancy.