thecontender's blog

By thecontender, history, 6 months ago, In English,

What is the time complexity of computing the square root of a n-digit number using Newton's method or binary search?

Thanks.

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

If I want to find square root of number a and abs(x - sqrt(a)) = O(eps) then abs(y - sqrt(a)) = O(eps2) where y = (x + a / x) / 2. The number of correct digits is multiplied by 2, so you need to do O(logn) steps to find the answer.

If you use binary search you need to do O(n) steps

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you considering the cost of multiplying/dividing n-digit numbers?