For the Power function below, time limit has exceeded. I can see other solutions to this problem here, but wanted to know why time limit exceeds with my implementation.
double Power(double x, int n)
{
if (n == 0) return 1;
if (x == 0) return 0;
double result = x;
int temp = n;
if (temp < 0)
{
temp = temp * -1;
}
for (int i = 1; i < temp; i++)
{
result *= x;
}
if (n < 0)
{
result = 1 / result;
}
return result;
}
Your algorithm is very slow for large values of n. You're doing n multiplications to get the power, so this is O(n) complexity.
p = x*x*x*...*x
\---------/
n times
You can speed up the calculation by grouping the values. For example you could calculate the square of x and then multiply that value n/2 times with itself (Note that you may need a single x in the end if n is odd).
x2 = x*x
p = x2*x2*...*x2 (*x)
\----------/
n/2 times
With this you only needed (n+1)/2+1 multiplications, which is O(n/2) and twice as fast in the limit of large n.
As you might guess, you can even further group the values and reuse those grouped powers, which leads to a O(log(n)) time complexity as @dbush pointed out in the comment to your question:
double Power(double x, int n) {
double result = 1.0;
double group;
if ( x == 0.0 ) {
return 0.0;
}
if ( n < 0 ) {
n = -n;
group = 1.0/x;
} else {
group = x;
}
while ( n > 0 ) {
if ( n % 2 ) {
result *= group;
}
n = n/2;
group *= group;
}
return result;
}
This algorithm keeps squaring the value of the group and multiply that group value to the result if needed.
Note There is a constant time O(1) implementation of the power function (e.g. the pow from math.h). This makes use of the fact that doubles only have a limited precision. The power can be written as
pow(x,n) = exp(n*log(x))
and the exponential exp as well as the natural logarithm log can be calulated in constant time (see my answer to this question for example). For small integer values of n, the above algorithm is faster though.
