I am working on an interview question from Amazon Software. The particular question I am working on is to write a program to find an.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.
Non-recursive method for finding a ^ n
java;recursion;interview questions;complexity
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}\$\$