title: Time Complexity of Efficient way to find power of a number
body: <p>I have written a small piece of code to find the power of a number </p>
  
  <p>Can any one tell me how to find the time complexity of this code.
  and what is the time complexity of this code. 
  and is it a efficient way to find powers of a number</p>
  
  <p>the code is : </p>
  
  <pre><code>public static void main(String[] args) {
  
          System.out.println(optPower(7, 15));    
      }
  
      static int optPower(int x, int y) {
          // divide in buckets
  
          if (y == 0) {
              return 1;
          }
          if (y == 1) {
              return x;
          }
          if (y == 2)
              return x * x;
  
          int tmpY;
  
          boolean isYmodified = false;
          if (y % 2 == 0) {
              tmpY = y;
          } else {
              tmpY = y - 1;
              isYmodified = true;
          }
  
          int biggestBucket = 2;
          int n = biggestBucket;
  
          /*
           * tmpY/4 , here '4' can be used as a tweking parameter to size the
           * buckets
           */
          while (tmpY % n == 0 &amp;&amp; tmpY / 4 &gt;= n) {
              biggestBucket = n;
              n = n * 2;
          }
  
          int res = 1;
          for (int i = 0; i &lt; biggestBucket; i++) {
              res = res * x;
          }
  
          int mul = res;
          for (int j = 1; j &lt; tmpY / biggestBucket; j++) {
              mul = mul * res;
          }
  
          return isYmodified ? mul * x : mul;
  
      }
  </code></pre>
  
  <p>As requested, I have added more notes for clearer explanation of the algorithm.</p>
  
  <p>if I want to compute <code>5</code> raise to <code>16</code></p>
  
  <p>step 1:-</p>
  
  <pre><code>5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5
  </code></pre>
  
  <p>here <code>x=5</code>, <code>y=16</code> in the above method</p>
  
  <p>if <code>y</code> is odd we multiple an extra <code>x</code> in the final result and assign <code>tmpY</code> as <code>y-1</code> to make it even</p>
  
  <pre><code>so noOfBuckets = 4 because of below code
  
  while (tmpY % n == 0 ) {
          biggestBucket = n;
          n = n * 2;
      }
      that is 
   16/(2 raise to 2)
  
  step 2:-
  
  divide 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5 into 4 buckets
  bucket1 :- 5,5,5,5
  bucket2 :- 5,5,5,5
  bucket3 :- 5,5,5,5
  bucket4 :- 5,5,5,5
  </code></pre>
  
  <p>step 3:-
   compute bucket 1 only and use the result of this bucket for remaining buckets
   result of bucket 1 = <code>625 = 5*5*5*5</code></p>
  
  <p>step 4 :-enter code here
   final result is <code>bucket1*bucket1*bucket1*bucket1</code> i.e <code>625 * 625 * 625 * 625</code> i.e. <code>5</code> raise to <code>16</code></p>
  
  <p>then we are avoiding iterations in bucket 2,3,4 and directly using the value from bucket 1 to get to the final result.</p>