1
$\begingroup$

What is the time complexity of Halley's Method?

I am thinking ${\cal O}(\log(n)F(n))$, or something very similar to Newton-Raphson, but I feel as though there should be some change to the complexity in order to yield the greater convergence. However, I can't seem to find any solid ground to support any of my ideas (as nobody has ever seemed to have asked this question on the internet before)...

Halley's Method - Wikipedia

$\endgroup$
  • 1
    $\begingroup$ What's $n$? Time complexity in what model of computation? $\endgroup$ – David Richerby Apr 11 '14 at 19:51
1
$\begingroup$

I'm assuming $n$ is the accuracy needed (in bits). Assuming that your starting point is reasonable, you converge in $O(\log n)$ iterations, just as in Newton's method. The absolute number of iterations is smaller than in Newton's method — Newton's method converges in $\log_2 n$ rounds, Halley's in $\log_3 n$ rounds (roughly speaking). However, this difference is lost in big O notation. For this reason, when analyzing methods like this, it is more meaningful to count function evaluations, keeping in mind that derivatives (and second derivatives in the case of Halley's method) may have a different complexity than the function itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.