Worst case time complexity of Math.sqrt in java

Question

We have a test exercise where you need to find out whether a given N number is a square of another number or no, with the smallest time complexity.

I wrote:

public static boolean what2(int n) {
    double newN = (double)n;
    double x = Math.sqrt(newN);
    int y = (int)x;
    if (y * y == n)
        return false;
    else
        return true;
}

I looked online and specifically on SO to try and find the complexity of sqrt but couldn't find it. This SO post is for C# and says its O(1), and this Java post says its O(1) but could potentially iterate over all doubles.

I'm trying to understand the worst time complexity of this method. All other operations are O(1) so this is the only factor. Would appreciate any feedback!

Answer 1

Using the floating point conversion is OK because java's int type is 32 bits and java's double type is the IEEE 64 bit format that can represent all values of 32 bit integers exactly.

If you were to implement your function for long, you would need to be more careful because many large long values are not represented exactly as doubles, so taking the square root and converting it to an integer type might not yield the actual square root.

All operations in your implementation execute in constant time, so the complexity of your solution is indeed O(1).

Answer 2

java's Math.sqrt actually delegates sqrt to StrictMath.java source code one of its implementations can be found here, by looking at sqrt function, it looks like the complexity is constant time. Look at while(r != 0) loop inside.

Answer 3

If I understood the question correctly, the Java instruction can be converted by just-in-time-compilation to use the native fsqrt instruction (however I don't know whether this is actually the case), which, according to this table, uses a bounded number of processor cycles, which means that the complexity would be O(1).