So, I just messed around with jsfiddler and played with the following algorithm to calculate sqrt without using 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/
Could you help me determine what the Big O complexity of the above algorithm would be? I tried and ended up somewhere around O (1/2 * LogN), but I'm not sure and really need some help. Thanks
solvable
As indicated above is a duplicate of the Babylonian method . I updated the code a bit to reflect the error threshold as follows:
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; }
and BigO result: O (log (log (x / error))
source share