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\$
  • 1
    \$\begingroup\$ What you may and may not do after receiving answers. I've partially rolled back your Rev 2 changes. \$\endgroup\$ – 200_success Feb 24 '15 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 '15 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\$ – committedandroider Feb 24 '15 at 18:30
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\$
  • \$\begingroup\$ What value is result initially set to in the first solution? \$\endgroup\$ – committedandroider Feb 24 '15 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\$ – committedandroider Feb 24 '15 at 6:21
  • \$\begingroup\$ What would space complexity be in the recursive solution? \$\endgroup\$ – committedandroider Feb 24 '15 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 '15 at 7:50
  • \$\begingroup\$ result must be initialized to 1. \$\endgroup\$ – orion Feb 24 '15 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\$
  • \$\begingroup\$ Yeah you're right. I should guard against that with an IllegalArgumentException \$\endgroup\$ – committedandroider Feb 23 '15 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.