Newton method. Initial guess of x. Iteratively update guess to be average of previous guess and x // guess. Since guess is too high, x guess is too low.Terminate when guess^2 <= x. Time - O((log x)^3) - log x from nb iterations, log x from multiple and log x from divide Space - O(1)

class Solution:

def mySqrt(self, x):

"""

:type x: int

:rtype: int

"""

guess = x

while guess * guess > x:

guess = (guess + x // guess) // 2

return guess