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, \2ドルn\$ 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.

• 200_success: What you may and may not do after receiving answers. I've partially rolled back your Rev 2 changes.
• orion: 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.
• committedandroider: no unsigned integer in java. stackoverflow.com/questions/9854166/…. My solution would be to have checker and an illegal argument exception

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}\$\$

• committedandroider: What value is result initially set to in the first solution?
• committedandroider: 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: What would space complexity be in the recursive solution?
• orion: 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: result must be initialized to 1.

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.

• committedandroider: Yeah you're right. I should guard against that with an IllegalArgumentException