Non-recursive method for finding $a^n$

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.

• What you may and may not do after receiving answers. I've partially rolled back your Rev 2 changes. – 200_success Feb 24 '15 at 2:31
• Remember, $a$ can be a double or even a complex number or a matrix. It's just $n$ that has to be an integer. And... just use an unsigned int. Negative arguments aren't valid for this algorithm. – orion Feb 24 '15 at 8:01
• no unsigned integer in java. stackoverflow.com/questions/9854166/…. My solution would be to have checker and an illegal argument exception – committedandroider Feb 24 '15 at 18:30

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}

• What value is result initially set to in the first solution? – committedandroider Feb 24 '15 at 6:14
• Can you optimize this further, in the same pattern, using the fact that $a^n = (a^3)^(n/3)$ now the function being in O($log_3n)$? – committedandroider Feb 24 '15 at 6:21
• What would space complexity be in the recursive solution? – committedandroider Feb 24 '15 at 6:28
• Space complexity in a recursive solution is proportional to the number of iterations because the recursive call frames are kept on the stack - $O(\log_2 n)$ for the squaring solution. And no, using a different base would make it worse. First of all, you live in a binary world so you are just looking which bytes are 1 (there is effectively no division and remainder operation - just bit shift and looking at the first bit). Secondly, this method achieves the optimal number of multiplications - bisection (which this is) gets there the fastest - dividing into more sections is always worse. – orion Feb 24 '15 at 7:50
• result must be initialized to 1. – orion Feb 24 '15 at 8:02
• 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.

• Yeah you're right. I should guard against that with an IllegalArgumentException – committedandroider Feb 23 '15 at 21:16