What is the complexity of babylonian method


  • 0
    T
    class Solution {
    public:
        int sqrt(int n) {
        double x = n;
        double y = 1;
        double e = 0.0000000001; /* e decides the accuracy level*/
        while(x - y >= e)
        {
            x = y + (x - y)/2;
            y = n/x;
        }
        return (int)(x);
        }
    };
    

    I have an accepted C++ solution for using babylonian method. Any clue what's the complexity? I see different results everywhere.


  • 0
    L

    In numerical analysis, IMHO, it's hard to determine the big O complexity defined in algorithm world. The time complexity determined by 1. the accuracy (e in your solution) and 2. how far n is away from 0 (The far the quicker).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.