I have a method similar to the following one:
public double[] foo(double[] doubleArray) {
DoubleStream stream = Arrays.stream(doubleArray);
return stream.map(s -> s / stream.sum()).toArray();
}
What is the complexity of this method? How many times will DoubleStream's sum method be executed? Once or O(n) times, with n = doubleArray.length?
This code will throw an exception, since you can't consume the same Stream more than once. You can only execute one terminal operation on a Stream.
If you change the code to:
public double[] foo(double[] doubleArray) {
return Arrays.stream(doubleArray).map(s -> s / Arrays.stream(doubleArray).sum()).toArray();
}
it will work, but the running time will be quadratic (O(n^2)), since the sum will be computed n times.
A better approach would be to compute the sum just once:
public double[] foo(double[] doubleArray) {
double sum = Arrays.stream(doubleArray).sum();
return Arrays.stream(doubleArray).map(s -> s / sum).toArray();
}
This will run in linear time.
linear time as I did. It doesn't matter if it's n or 2n or cn. All are linear time.