would I find the recurrence relation(or so called recursion equation) for the following code, and how would that help me get "average time analysis" for big Theta notation? double func3(int[] A) { int count = 0; int sum = 0; Random prng = new Random(); for (int i=0; count < 25 && i < A.length; i++) { if (prng.nextDouble() < 0.5){ count++; sum+=A[i]; } } return sum / 25.0;
How would I find the recurrence relation(or so called recursion equation) for the following code, and how would that help me get "average time analysis" for big Theta notation?
double func3(int[] A) {
int count = 0;
int sum = 0;
Random prng = new Random();
for (int i=0; count < 25 && i < A.length; i++) {
if (prng.nextDouble() < 0.5){
count++;
sum+=A[i];
}
}
return sum / 25.0;
}
what I had got so far is that
this function would iterate for the half of the length of the data array that is passed(int[] A)
until input array A reaches length of 50, where it will start to get stuck to the 25 iteration for average which is limited by count<25 condition
so the recurrence relation would be something like
1. f(x) = 0, when the x reaches the recursion stack that the anymore recursion would not affect sum anymore(reaches 25 count)
2.f(x) = f(x+1) +1/2 , x>0 something like this, that it would make progress toward base case.
I am not sure this would be the right form, but I am pretty sure this would be something like this.
and based on this, I could find that this would be Theta(n) for the loop until data array length of 50,
but be constant of 25 iterations after then.
How would I summary this to one reccurence relation with notation of Theta for the average running time analysis?
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
