LeetCode #69 Sqrt(x)

Easy

Problem

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

Solution — Binary Search

Use binary search to find the number whose square is less or equal to x.

Complexity

Binary search divides search domain in half, so time complexity is O(logx).

It’s trivial that space complexity is O(1).

Solution — Newton’s Method

By Newton’s method, we can find approximated root for x. It’s noted that we only have to check upper bound and make sure the precision will be less than one.

Complexity

The space complexity is obviously O(1).

Time complexity is too hard for me to estimate. My intuition is O(logx) because we divide 2 every time but I can’t give a strong evidence to support this guess.

Please tell me if someone has any idea of proof, many thanks.