RunTime Complexity of my Power method

Viewed 763

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);
    }
2 Answers
Related