What is the time complexity of this square root calculation?

Question

I needed a square root approximation in C so I looked up this post and got this following implementation:

float squareroot(float n)
{
    float x = n;
    float y = 1;
    float e = 0.001; // Accuracy level
    if (n == 0)
        return 0;
    while ((x - y) > e)
    {
        x = (x + y) / 2;
        if (n == 0 || x == 0)
            return 0;
        y = n / x;
    }
    return x; 
}

What is the time complexity of this?

Answer 1

Hint:

Observe that

(x[k+1] - √n)/(x[k+1] + √n) = (x[k] + n/x[k] - 2√n)/(x[k] + n/x[k] + 2√n) 
                            = (x[k] - √n)²/(x[k] + √n)².

So by induction,

(x[k] - √n)/(x[k] + √n) = (x[0] - √n)^(2^k)/(x[0] + √n)^(2^k)
                        = (√n - 1)^(2^k)/(√n + 1)^(2^k).

From this we find the number of iterations after which the error is e:

k = lg(lg(e / (2√n - e)) / lg((√n - 1)/(√n + 1)).

(base-2 logarithm.)