Time Complexity of Halley's Method
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 &mdash; 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.