In CS, we had to emulate an HP 35 calculator, so I looked up a summation for e^x [in this case '^' means "to the power of"]. The formula is sum n=0 to infinity ( (x^n) / (n!) )
In my implementation, the first for loop is the summation loop: 1 + x + x^2 /2! + x^3 /3! + ..., and the second for loop is used to individually multiply out the x term, so as to not overflow the double: ... + (x/3) * (x/2) * (x/1) + ...
In regards to time complexity, the first for loop is only necessary to ensure the necessary accuracy, but the second for loop is used to multiply out the terms. Neither of the loops are directly influenced by the size of x so I don't know how to calculate the time complexity on this algorithm; I suspect it is n ln(n). How do I calculate/ What is the time complexity for this algorithm
public class TrancendentalFunctions {
private static final double ACCURACY = .000000000000001;
public static double exp(double x) {
// if larger than 709, throw overflow error
double result = 1; // result starts at one is important
for(int i=1; i < 2147483647; i++) {
double temp = 1; // temp starts at one is important
for(int n = i; n > 0; n--) {
temp *= x / n;
}
result += temp;
if (temp < ACCURACY) break; // accuracy of 14 digits
}
return result;
}
}
The algorithm runs in O(1) time since the amount of work you perform is bounded (albeit by a huge value).
If you treat the outer loop (over i) as infinite rather than bounded, then the inner loop (over n) performs i units of work. The outer loop is executed until x^i/i! is less than ACCURACY.
Using Stirling's approximation for i!, gives an approximation for x^i/i! as (1/sqrt(2*pi*i)) * (e*x/i)^i.
(Hand-waving, although I believe this can be formalized) For large x, this is going to be true around the point where e*x/i < 1 (since as soon as that's true the value of x^i/i! will quickly get smaller than ACCURACY). That happens when i = e*x.
So the outer loop will execute O(x) times, giving a total run-time of O(x^2).
There's an obvious improvement to reduce the runtime to O(x). Instead of computing x^i/i! each time, reuse the previous value.
double temp = 1;
double result = 1;
for (int i = 1; true; i++) {
temp *= x / i;
result += temp;
if (Math.abs(temp) < ACCURACY) break;
}
return result;