Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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)...
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.
