CODEWITHSUNDEEP
javatime-complexity
JavaDeveloper
JavaDeveloper

Reputation: 5660

Time complexity of Math.sqrt Java

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.

Upvotes: 4

Views: 5471

Answers (2)

emory
emory

Reputation: 10891

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.

Upvotes: 2

Evan Bechtol
Evan Bechtol

Reputation: 2865

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?

Upvotes: 3

Related Questions