Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java Math.pow(a,b) time complexity

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]);

   }
}
like image 530
seriously divergent Avatar asked Sep 05 '15 23:09

seriously divergent


People also ask

What is the time complexity of Math POW in Java?

You can safely assume that it is O(1) .

What is the time complexity of POW?

Time Complexity: O(N) because pow(x,n) is called recursively for each number from 1 to n. Space Complexity: O(1) No extra space has been used.

Is Math POW double or int?

pow Example. The method raises a to the power of b and returns the result as double. In other words, a is multiplied by itself b times.

What is pow () in Java?

pow() is used to calculate a number raise to the power of some other number. This function accepts two parameters and returns the value of first parameter raised to the second parameter.


1 Answers

@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) selected1 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.

like image 74
Stephen C Avatar answered Oct 02 '22 05:10

Stephen C