5
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ What you may and may not do after receiving answers. I've partially rolled back your Rev 2 changes. \$\endgroup\$ Feb 24, 2015 at 2:31
  • \$\begingroup\$ 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. \$\endgroup\$
    – orion
    Feb 24, 2015 at 8:01
  • \$\begingroup\$ no unsigned integer in java. stackoverflow.com/questions/9854166/…. My solution would be to have checker and an illegal argument exception \$\endgroup\$ Feb 24, 2015 at 18:30

2 Answers 2

6
\$\begingroup\$

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

\$\endgroup\$
13
  • \$\begingroup\$ What value is result initially set to in the first solution? \$\endgroup\$ Feb 24, 2015 at 6:14
  • \$\begingroup\$ 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)\$? \$\endgroup\$ Feb 24, 2015 at 6:21
  • \$\begingroup\$ What would space complexity be in the recursive solution? \$\endgroup\$ Feb 24, 2015 at 6:28
  • \$\begingroup\$ 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. \$\endgroup\$
    – orion
    Feb 24, 2015 at 7:50
  • \$\begingroup\$ result must be initialized to 1. \$\endgroup\$
    – orion
    Feb 24, 2015 at 8:02
4
\$\begingroup\$
  • 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.

\$\endgroup\$
1
  • \$\begingroup\$ Yeah you're right. I should guard against that with an IllegalArgumentException \$\endgroup\$ Feb 23, 2015 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.