LeetCode #367 Valid Perfect Square

Easy

Problem

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Output: true

Example 2:

Input: 14
Output: false

Solution — Binary Search

By using binary search, we can easily check is there is a number whose square is num.

Complexity

It’s trivial that binary search takes O(logn) time which n is num in this problem. And it’s also clear that it uses only O(1) extra space.

Solution — Newton’s method

Like #69, you can also choose Newton’s method to find the closest root.

Complexity

The space complexity is O(1).

However, like #69, I have no idea how to estimate its time complexity. It will be great if you can help me to figure out its time complexity, many thanks.