1. Dichotomy def sqrt(x, e=1e-6): if x<0: return -1 # error if x==0: return 0 if x < 1: a, b = x, 1 else: a, b = 0, x while b-a > e: m = (a+b)/2 if m*m > x: b = m else: a = m return (a+b)/2 Time complexity: $$ \frac{x}{2^{f(n)}} < e \ f(n) > log2(x/e) $$ Since e is usually a fixed number, the time complexity is $O(log(x))$
