what is Newton-Raphson Square Method's time complexity?

What is the time complexity of the New开发者_运维百科ton-Raphson square method?

• Wikipedia: Newton's method

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 gives a relevant approach as to how to consider the method's complexity.

Newton Raphson Method is an algorithm to solve for the roots of a transcendental equation.

formula: Newton Raphson Method Formula

If an accurate initial approximation is provided to us and the roots of the equation exists then, the complexity of Newton Raphson Method is O(n) and the best case would be Θ(log(n)).

First we apply a first level of Newton’s method to solve f(x) = sin(x) - 3x^2 . Each iteration of the given equation requires division of slope with actual value.

If we set the precision of the final answer to m digits right from the start, then convergence at the first level will require log(m) iterations. This means the complexity of computing a square root will be Θ(m^α * log(m)) if the complexity of multiplication is Θ(m^α), given that we have shown that the complexity of division is the same as the complexity of multiplication.

the time complexity of m-digit division is Θ(m^α),