Блог пользователя thecontender

Time complexity of computing the square root of a n-digit number?
Автор thecontender, история, 5 лет назад, По-английски

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

Thanks.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить