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
.