I am not a math student, so I don’t fully understand the complexity as mentioned on Wiki for Newton Raphson method for finding square root. But I wrote a computer program for Newton-Raphson’s method and tried to run on increasing values.
/*Code Snippet */ x = n = 100; y = 1 i = 0; while x > y: x = (x+y)/2 y = n/x i = i + 1 print "Iterations for convergence: ", i
Values: ( All log values are base 2)*
N=10000 , Iterations : 9 , log(N) = 13.28
N=100000000 , Iterations : 16 , log(N) = 26.57
N=10000000000000000 , Iterations : 30 , log(N) = 53.15
…..and so on…..Assuming the 2 division takes constant value , is the complexity of the method less than log(N)? Atleast that is what I could see from my values. Can someone please try to answer in layman terms if NR method is less than logN or it is greater than equal to logN. You can assume for perfect squares for now.