Power(base, exponent)
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*********************************************************************
 * Author: Isai Damier
 * Title: Power(base, exponent)
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement: Compute base x raised to exponent n: x^n
 *
 * Sample Input: 3^11
 * Sample Output: 177147
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(Time) = O(log n),
 *
 * Technical Details:
 *   Instead of multiplying x by itself n times using a for-loop,
 *   we continually divide the exponent by two (think binary search)
 *   hence reducing the time complexity to O(log n) instead of O(n).
 *   We demonstrate by manually solving for 3^11.
 *
 *   3^11 = 3^5 * 3^5 * 3
 *   3^5 = 3^2 * 3^2 * 3
 *   3^2 = 3 * 3 = 9
 *
 *  Therefore, we perform five multiplications instead of eleven:
 *  3*3=9; 9*9*3 = 243; 243*243*3 = 177147
 *
 ********************************************************************/
 public int pow(int base, int exponent) {
    if (1 == exponent) {
        return base;
    }
    int result = pow(base, exponent / 2);
    if (0 == (exponent & 1)) {
        return result * result;
    }
    return result * result * base;
}