Computational complexity of Newtons Method

Question

I'm trying to do a worst case complexity analsis of another algorithm that involves computing an nth root of a real number at each step. I have a bound B on the size of this number also n is fixed and I'm computing the nth root to fixed precision (say 10 digits). I'm not sure how to go about including this in analysis. What is the time complexity of using newtons method to compute the nth root of these numbers in terms of B?

Answer 1

Each iteration roughly squares the error, because the method is based on ignoring terms that are O(x^2). Therefore, to get 10 digits takes one more iteration than to get 5 digits, which takes one more iteration than to get 2.5 digits, and so on back to the accuracy of your initial guess. I doubt you will need more than 7 iterations. It's a very fast convergence.

For large n, the computational complexity of a single iteration is dominated by the time to compute x^(n-1). This requires roughly log(n) multiplications.

Since you say n and the precision are fixed, and assuming you have a good initial guess, you can treat the entire algorithm as O(1). It will not behave badly. But you do need a reasonably good initial guess.