1
$\begingroup$

In the context of root finding, it is often stated that the bisection method is slower than Newton's method due to linear convergence. However, I am trying to understand why this is the case from an algorithmic time complexity viewpoint.

My understanding is that the time complexity of Newton's method is $O(log(N)F(N))$ where $F(N)$ is the cost of calculating $\frac{f(x)}{f'(x)}$ with $N$-digit precision. But given the architecture of the bisection method, which halves the search interval at each iteration, I was under the impression that its time complexity was also logarithmic. I was therefore wondering whether anyone could shed some light on why the bisection method is slower than Newton's method from a complexity point of view? Any comments or references to literature would be greatly appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ "I was under the impression that its time complexity was also logarithmic": just an impression, it is linear in the number of digits (exactly one bit per function evaluation). $\endgroup$
    – user65203
    Commented Feb 19, 2016 at 8:00

1 Answer 1

2
$\begingroup$

Per every bit you need one bisection step, so the cost is $\sim N·eval(f)$, while Newton is, as you wrote, $\sim 3·\log(N)·eval(f)$, where it is used that $eval(f,f')=3·eval(f)$ if automatic/algorithmic differentiation is used.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .