performance - Time complexity for Babylonian Method

Question

What would be the time complexity for Babylonian Method? is it log(n) where n is the number we want to find the squared root for? If so, why is this so?

Answer 1

Looking at the wikipedia section for the Babylonian method we can see that the relative error at step k, e_k, satisfies the equation e_k < 2^-f(k), where f(k) is defined recursively as follows:

f(1) = 2 and f(k+1) = 2 * f(k) + 1 for n > 1

By induction, f(k) = 3 * 2^k-1 - 1

Let n be the input to our algorithm, which stops when we are sure that the total error is less than a constant m

The error at step k, E_k, satisfies the equation E_k = e_k * n

Therefore the algorithm will terminate once e_k * n < m

This will occur when 2^f(k) > n/m which is equivalent to f(k) > log₂(n/m)

That equation is true when 2^k-1 > (log₂(n/m) - 1)/3 which is true when k > log₂((log₂(n/m) - 1)/3)+ 1

Therefore the algorithm will terminate in O(log(log(n/m)+1)) steps.

Using this logarithmic summation formula you can show that log(log(x)+c)) = O(log(log(x)).

Therefore the Babylonian method takes O(log(log(n/m)) steps

Answer 2

I guess steps would be O(log2(log to the base E0 (m/n)) where E0 is the error at zeroth iteration i.e when we choose seed value m is error allowed in the ans and n is the input to the algorithm. You can refer to this for complete explanation for recursive function of error :http://www.math.harvard.edu/library/sternberg/slides/lec1.pdf