Time complexity for square root using Newton's method

Question

I have written a java program to find square root of a given number using newton's method.This program works exactly as intended But I am not good at time complexity.

So can you please tell me what is the time complexity of following program. Suggestions are welcomed to improve it.

What is the Big O notation for sqrt method?

/**Find square root of a number using Newton's method**/
/**Specify number of correct precision required in a square root**/
/**Also specify maxIterations limit so that program won't go into into infinity loop**/
import java.util.*;
public class SqrtNewton{
        public static void main(String[] args){
            try{
                long startTime = System.nanoTime();
                Scanner scanner = new Scanner(System.in);
                //Number for which square root has to be found
                System.out.println("Enter number - ");
                long number = scanner.nextLong();
                //Maximum no of iterations if program does not found Square root untill then
                int maxIterations = 40; 
                //precision value to untill correct square root is required
                int precision = 3;
                //Value of x to start with for newton's method
                double x = 1;
                //Negative numbers do not have square roots
                if (number < 0) throw new IllegalArgumentException("Provided value is invalid");
                //iteration start
                int itr = 0;
                //epsilon value to check equality of double value untill given precision
                double epsilon = Math.pow(10,-precision);
                double squareRoot = sqrt(number,maxIterations,x,itr,epsilon);
                System.out.println("Square Root Of "+number+" With correct precision "+precision+" is :- "+squareRoot);
                System.out.printf("Square Root Of %d With correct precision %d is :- %."+precision+"f",number,precision,squareRoot);
                System.out.println();
                long endTime = System.nanoTime();
                System.out.println("Total Running Time - "+(endTime - startTime));
            }catch(Exception e){
                //e.printStackTrace();
                System.err.println("Exception - "+e.getMessage());
            }
        }
        private static double sqrt(long number,int maxIterations,double x,int itr,double epsilon) throws MaxIterationsReachedException{
            if(itr >= maxIterations){
                throw new MaxIterationsReachedException(maxIterations);
            }else{
                double x1 = (x + (number/x))/2;
                /**To check equality of double number untill given precision**/
                /**This will check 1.1333334 - 1.1333334 < 0.000001(if precision is 6)**/
                if(Math.abs(x1 - x) <=  epsilon){
                    System.out.println("Total Iterations - "+itr);
                    return x1;
                }
                else
                    return sqrt(number,maxIterations,x1,++itr,epsilon);
            }
        }
}


class MaxIterationsReachedException extends Exception{  
 MaxIterationsReachedException(int maxIterations){
     super("Maximum iterations limit "+maxIterations+" reached Increase maxIterations limit if required");
 }
} 

Answer 1

Your code is an implementation of Newton method for solving x^2-c = 0.

That is known to have quadratic convergence, which means if you want D digits of accuracy, it'll take roughly log(D) iterations, although this depends on your initial guess for the square root in a complicated way. You can read the proof of quadratic convergence on wikipedia: https://en.wikipedia.org/wiki/Newton%27s_method which includes preconditions for quadratic convergence.

Since your initial guess is always "1", this will probably not satisfy the conditions for quadratic convergence, and if my memory is correct, this means that for large x, there'll be some slow convergence for some steps, followed by the fast quadratic convergence. Working out the details of the actual time complexity is quite involved, and probably beyond what you want.

Answer 2

I would say the complexity is O(n) with n is the maxIterations. You don't need to write this algorithm in recursive way, you can use a loop like this:

private static double sqrt2(long number, int maxIterations, double x, int itr, double epsilon)
        throws MaxIterationsReachedException {
    double x1 = (x + (number / x)) / 2;
    while (Math.abs(x1 - x) > epsilon) {
        if (itr >= maxIterations) {
            throw new MaxIterationsReachedException(maxIterations);
        }
        x = x1;
        x1 = (x + (number / x)) / 2;
        itr++;
    }
    System.out.println("Total Iterations - " + itr);
    return x1;
}