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!
Using the floating point conversion is OK because java's
int
type is 32 bits and java'sdouble
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 largelong
values are not represented exactly asdouble
s, 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).