@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:

  Copy* 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.}

Answering that question depends on what you consider the complexity of Math.pow(). For most hardware, it's O(1), but on a theoretical Turing machine, it isn't. Let's assume it's free.

Let's consider the loop. The complexity is going to be a function describing how many times the loop runs, given N. The loop starts with i=0, adds 1 to i each time, and continues while Math.pow(2,i) < N. Let's consider some cases.

N is 0, loop runs 0 times.

N is 1, loop runs 1 time because the second time, 2^1 > 1.

N is 2, loop runs 2 times, 2^2 > 2.N is 3, loop runs 2 times, 2^2 > 3.

N is 4, loop runs 3 times, 2^3 > 4.

N is 5, loop runs 3 times, 2^3 > 5.

N is 6, loop runs 3 times, 2^3 > 6.

N is 7, loop runs 3 times, 2^3 > 7.

N is 8, loop runs 4 times, 2^4 > 8

N is 100, loop runs 7 times, 2^7 > 100

N is 1000, loop runs 10 times, 2^10 > 1000

Okay, so a function that describes this growth looks to be the opposite of taking an exponent. That's logarithms. O(log(N)) is probably right. Let's verify, remembering that in CS, we tend to assume log in base-2.

N is 2, loop runs 2 times, log(2) is 1

N is 3, loop runs 2 times, log(3) is ~1.5

N is 4, loop runs 3 times, log(4) is 2

N is 5, loop runs 3 times, log(5) is ~2.3

N is 6, loop runs 3 times, log(6) is ~2.5

N is 100, loop runs 7 times,log(100) is ~6.6

N is 1000, loop runs 10 times, log(1000) is ~9.9

Yep, it's O(log(N)).

All that said, I already knew it would be O(log(N)) because of a useful shortcut. If your for loop iterates through every value from 1 to N, that's always going to be O(N). If your for loop does N times N times, that's O(N^(2)). And, most importantly, if your loop gets halfway to the end with every step, that's O(log(N)) for sure. Walking twice as far with every step to a target is the same thing as walking a number down to zero by removing a bit each time, which is the same thing as walking halfway to your goal (removing a bit is the same as dividing by 2).

how is that possible, please

Because Math.pow is JVM intrinsic, that is, JIT-compiler inlines the call. Furthermore, when it sees that exponent is a constant 2, it replaces the call with exactly x*x.

Proof from HotSpot sources

Its O(n), where n is the length of the character array digits. Since the loop will iterate that no of times the next line is a if else clause which will execute only once.