1

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?

Andy
  • 11
  • 6
  • [See also](https://stackoverflow.com/questions/2637700/is-it-possible-to-roll-a-significantly-faster-version-of-sqrt) - seems you're not really asking about the time complexity (theory). – 500 - Internal Server Error Sep 19 '22 at 10:56
  • 3
    The `n == 0` in `if (n == 0 || x == 0)` is never true. – chux - Reinstate Monica Sep 19 '22 at 10:59
  • 1
    The code is (I think) incorrect, because the termination condition should be `fabs(x-y) < e`. With the fix, it is O(log n) according to https://math.stackexchange.com/questions/558145/minimum-number-of-iterations-in-newtons-method-to-find-a-square-root – Paul Hankin Sep 19 '22 at 11:14
  • @PaulHankin : In general this is true, but here you have that the babylonian-Heron-Newton method for the square root produces a sequence of `x` that approximates the root from above in a falling sequence, and thus `y` will always be below the root and thus smaller than `x`. – Lutz Lehmann Sep 19 '22 at 12:35
  • 1
    @LutzLehmann yes, assuming n>1. – Paul Hankin Sep 19 '22 at 12:46

1 Answers1

0

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