Java Math.pow(a,b) time complexity

Question

I would like to ask time complexity of the following code. Is it O(n)? (Is time complexity of Math.pow() O(1)? ) In general, is Math.pow(a,b) has time complexity O(b) or O(1)? Thanks in advance.

public void foo(int[] ar) {
   int n = ar.length;
   int sum = 0;
   for(int i = 0; i < n; ++i) {

     sum += Math.pow(10,ar[i]);

   }
}

Answer 1

You can consider Math.pow to be O(1).

There's a few possible implementations, ranging from a CPU assembler instruction (Java doesn't use this) to a stable software implementation based on (for example) the Taylor series expansion over a few terms (though not exactly the Taylor implementation, there's some more specific algorithms).

It most definitely won't repeatedly multiply if that's what you're worried about.

Answer 2

@Blindy talks about possible approaches that Java could take in implementing pow.

First of all, the general case cannot be repeated multiplication. It won't work for the general case where the exponent is not an integer. (The signature for pow is Math.pow(double, double)!)

In the OpenJDK 8 codebase, the native code implementation for pow can work in two ways:

• The first implementation in e_pow.c uses a power series. The approach is described in the C comments as follows:

  * Method:  Let x =  2   * (1+f)
  *      1. Compute and return log2(x) in two pieces:
  *              log2(x) = w1 + w2,
  *         where w1 has 53-24 = 29 bit trailing zeros.
  *      2. Perform y*log2(x) = n+y' by simulating multi-precision
  *         arithmetic, where |y'|<=0.5.
  *      3. Return x**y = 2**n*exp(y'*log2)
  

• The second implementation in w_pow.c is a wrapper for the pow function provided by the Standard C library. The wrapper deals with edge cases.

Now it is possible that the Standard C library uses CPU specific math instructions. If it did, and the JDK build (or runtime) selected¹ the second implementation, then Java would use those instructions too.

But either way, I can see no trace of any special case code that uses repeated multiplication. You can safely assume that it is O(1).

---

^{1 - I haven't delved into how when the selection is / can be made.}