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?

CodePudding user response：

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.)