Question: What is the time complexity of the Newton-Raphson square method?

* [Wikipedia: Newton's method](http://en.wikipedia.org/wiki/Newton%27s_method)

Answer: 
From <http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity>:

> 
> Using Newton's method as described
>  above, the time complexity of
>  calculating a root of a function f(x)
>  with n-digit precision, provided that
>  a good initial approximation is known,
>  is O((\log n) F(n)) where F(n) is the
>  cost of calculating f(x)/f'(x)\, with
>  n-digit precision.
> 
> 
> 

However, depending on your precision requirements, you can do better:

> 
> If f(x) can be evaluated with variable
>  precision, the algorithm can be
>  improved. Because of the
>  "self-correcting" nature of Newton's
>  method, meaning that it is unaffected
>  by small perturbations once it has
>  reached the stage of quadratic
>  convergence, it is only necessary to
>  use m-digit precision at a step where
>  the approximation has m-digit
>  accuracy. Hence, the first iteration
>  can be performed with a precision
>  twice as high as the accuracy of x\_0,
>  the second iteration with a precision
>  four times as high, and so on. If the
>  precision levels are chosen suitably,
>  only the final iteration requires
>  f(x)/f'(x)\, to be evaluated at full
>  n-digit precision. Provided that F(n)
>  grows superlinearly, which is the case
>  in practice, the cost of finding a
>  root is therefore only O(F(n)), with a
>  constant factor close to unity.
> 
> 
>
This [article](http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity) gives a relevant approach as to how to consider the method's complexity.