thecontender's blog

Time complexity of computing the square root of a n-digit number?
By thecontender, history, 5 years 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

Comments Comments (1)
| Write comment?
»
5 years 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

→ Reply