From http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity :
Using the Newton method, as described above, the time complexity of computing the root of the function f (x) with n-bit precision, provided that a good initial approximation is known, is O ((\ log n) F (n)), where F (n ) is the cost of computing f (x) / f '(x) \, with n-bit precision.
However, depending on your accuracy requirements, you can do better:
If f (x) can be estimated with variable accuracy, the algorithm can be improved. Due to Newton’s “self-correcting” nature, the method, which means that it is not influenced by small perturbations, when it reaches the stage of quadratic convergence, you only need to use m-bit accuracy at the step where the approximation has m-discharge accuracy. Therefore, the first iteration can be performed with an accuracy two times higher than the accuracy x_0, the second iteration with an accuracy four times higher, etc. If the exact levels are chosen appropriately, only the final iteration f (x) / f '(x) \ is required, which should be evaluated at full n-bit accuracy. Provided that F (n) grows superlinear, which in practice takes the search costs, therefore the root is O (F (n)), with a constant factor close to unity.