What is time-complexity of math.sqrt implementation in Java ? Java has time-complexity implemented in some technique whose, time-complexity I am trying to determine.
Asked
Active
Viewed 5,195 times
4
-
Please try to elaborate on what your problem is. The description you gave is hard to grasp. – Daniel S. Mar 02 '15 at 17:01
-
I'd imagine it would use Newton's method (or some other similar numerical analysis method). – But I'm Not A Wrapper Class Mar 02 '15 at 17:02
-
I would suggest to check this: http://stackoverflow.com/questions/16232629/what-is-time-complexity-and-how-to-find-it It's very well-explained and can give you good knowledge of what you want to do. – Marcelo Tataje Mar 02 '15 at 17:04
2 Answers
3
In most cases, Java attempts to use the "smart-power" algorithm, which results in a time-complexity of O(log n). Smart power Algorithm
Also, it appears that in different cases, you could end up with different complexities; Why is multiplied many times faster than taking the square root?
Community
- 1
- 1
Evan Bechtol
- 2,855
- 2
- 18
- 36
-
1from the [source code](https://developer.classpath.org/doc/java/lang/StrictMath-source.html), Math.sqrt will use bit operation trick and directly determine every bit in sqrt(n), which is at most O(64) ~ O(1) – maplemaple Jun 19 '21 at 19:18
2
It looks like it is implemented by delegating to the sqrt method StrictMath which is a native method.
Thus it seems the answer would be implementation specific.
Strictly speaking it is O(1). In theory (but obviously not practice), we could iterate over all doubles and find the maximum time.
In addition, the time complexity of Math.sqrt(n) does not directly depend on n but instead on the amount of space needed to represent n which for doubles should be constant.
emory
- 10,725
- 2
- 30
- 58
-
This should be [the definition of `StrictMath.sqrt`](http://stackoverflow.com/questions/825221/where-can-i-find-the-source-code-for-javas-square-root-function) – But I'm Not A Wrapper Class Mar 02 '15 at 17:17