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