RunTime Complexity of my Power method

Question

This is my implementation of the power method.

1. If the power is an even number, I square the base, and divide the power by 2.

2. If the power is an odd number, I run the method recursively, with the power reduced by 1, so as to get an even number, and multiply the result by base, to account for the power reduced by one.

3. The base case is reached when the power is 1, and the result is 0.

My question is, what is the time complexity of this method? Since, we're dividing the power by 2, on every iteration, is it logn to the base 2 ?

      double myPow(double base, int pow) {
      if(pow == 0)
          return 1;

      if(pow < 0)
          return 1/base * 1/myPow(base, (pow*-1)-1);

      if(pow %2 == 1)
          return base * myPow(base, pow-1);
      else
          return myPow(base*base, pow/2);
    }

Answer 1

Yes, complexity is logarithmic. Your method is essentially exponentiation by squaring

Number of squarings is equal to the number of zeros in binary expansion of pow, and number of multiplications is equal to the number of ones in binary expansion of pow, so overall number of operations is about the number of significant bits of pow, log2(pow)