AppliedNumeric answerFree solution

Starting from the bracket [0,5][0, 5], how many bisection steps are needed to locate a root to within 10−610^{-6}?

Answer with a number. Fractions, powers and expressions like 23/6 or C(52,5) are read correctly in practice.

Show the answer and worked solution

Answer

2323

Bisection halves the bracket every step, so after nn steps the interval is (b−a)/2n(b-a)/2^n and you need 5/2n≤10−65/2^n \le 10^{-6}, that is n≥log⁡2(5×106)≈22.25n \ge \log_2(5 \times 10^6) \approx 22.25, so 2323 steps. The method gains exactly one bit of accuracy per iteration regardless of the function, which is its great virtue: guaranteed convergence at a known, unimpressive rate. Newton gains roughly double the digits per step but can diverge, which is why production solvers run Newton inside a maintained bracket and fall back to bisection when a step leaves it.

Worked solution

  1. Formula
    b−a2n≤ε ⇒ n≥log⁡2b−aε\frac{b-a}{2^n} \le \varepsilon \ \Rightarrow\ n \ge \log_2\frac{b-a}{\varepsilon}
  2. Substitute
    n≥log⁡2510−6=log⁡2(5×106)n \ge \log_2\frac{5}{10^{-6}} = \log_2(5 \times 10^{6})
  3. Solve
    ≈22.25\approx 22.25
  4. Answer
    23 steps23 \text{ steps}

Sanity check. Newton would take four or five from a decent guess, which is why bisection is the fallback rather than the algorithm.

Takeaway: Bisection gains one bit per step.

Answer it in practice – your answer is marked and recorded.

Reported in interviews at

Optiver, IMC Trading, Akuna Capital

More numerical methods questions

Starting from the bracket [0,5], how many bisection steps are needed to locate… · QuantMax