Non-recursive method for finding \$a^n\$

Question

I am working on an interview question from Amazon Software. The particular question I am working on is "to write a program to find \$a^n\$."

Here is my recursive solution to this problem (in Java):

int pow(int a, int n) {
     if(n == 0) {
          return 1;
     } else {
          return a * pow(a, n -1 );
     }         
}

I did some runtime analysis and found that this solution runs in \$O(n)\$ time - recurrence relation with \$T(n) = 3 + T(n-1)\$, \$T(0)=1\$, and \$O(n)\$ space - depth of memory stack is \$n\$, with two local variables at each call, \$2n\$ total.

We are always taught to optimize our code in terms of space complexity and time complexity, so here is another solution that I came up with:

int pow(int a, int n) {
     int result = 1;
     for(int count=0;count<n;count++) {
           result *= a;
     }
     return result;
}

Would this solution be more efficient than the first one? This one runs in \$O(n)\$ time-loop until \$n\$ and \$O(1)\$ space - four units of space - one for a, n, result, and count.

Answer 1

There is a more efficient method using squaring:

int result = 1;
while(n>0){
    if(n%2 == 1)result*=a;
    a *= a;
    n /= 2;
}

Or in recursive notation:

int pow(int base, int exponent) {
     if(exponent == 0) {
          return 1;
     } else if(exponent%2 == 1){
          return base * pow(base*base, exponent / 2 );
     } else {
          return pow(base*base, exponent / 2 );
     }
}

This works because

\$\$ a^n = \begin{cases} (a^2)^{\frac{n}{2}} & \text{if $n$ is even} \\ a \cdot (a^2)^{\frac{n-1}{2}} & \text{if $n$ is odd} \end{cases}\$\$

Answer 2

• n is int, which means it could be negative. The recursive version would run forever, and an iterative version would produce a wrong result.

• Complexity analysis of your algorithms is correct, however...

• ... I don't want to spoil your pleasure of finding a \$O(\log{n})\$ solution - just keep in mind that it is possible.