找出这个循环的大O.

Question

所以我只是搞乱了jsfiddler,并使用以下算法来计算,sqrt而不使用Math.sqrt:

var counter = 0;

function sqrt(x){
    var a, b;

    a = 1;
    b = x;
    while (Math.abs(a - b) > 0.1){
        a = (a + b) / 2;
        b = x / a;
        counter++;
    }

    return a;
}

var x = 64;
var result = sqrt(x);

alert('Result = ' + result + ' (number of iterations ' + counter + ')');

的jsfiddle:

http://jsfiddle.net/2wx99yxj/

你能帮我确定一下上述算法的Big O复杂度吗？我试过并在O(1/2*LogN)附近结束但我不确定并且实际上需要一些帮助.谢谢

解决了

如上所述 - 巴比伦方法的复制品.我稍微更新了代码以反映error threshold如下:

function sqrt(x){
    var a, b, error;

    error = 0.1;
    a = 1;
    b = x;
    while (Math.abs(a - b) > error){
        a = (a + b) / 2;
        b = x / a;
        counter++;
    }

    return a;
}

而BigO的结果是:O(log(log(x/error))