Someone asked me a brainteaser, and I don't know; my knowledge slows down after amortized analysis, and in this case, this is O(n).
public int findMax(array) {
int count = 0;
int max = array[0];
for (int i=0; i<array.length; i++) {
if (array[i] > max) {
count++;
max = array[i];
}
}
return count;
}
What's the expected value of count
for an array of size n?
Numbers are randomly picked from a uniform distribution.
I would like to comment on Nemo's answer, but I don't have the reputation to comment. His correct answer can be simplified:
The chance that the second number is larger than the first is 1/2. Regardless of that, the chance that the 3rd number is larger than two before, is 1/3. These are all independent chances and the total expectation is therefore
1/2 + 1/3 + 1/4 + .. + 1/n
Let f(n) be the average number of assignments.
Then if the last element is not the largest, f(n) = f(n-1).
If the last element is the largest, then f(n) = f(n-1) + 1.
Since the last number is largest with probability 1/n
, and not the largest with probability (n-1)/n
, we have:
f(n) = (n-1)/n*f(n-1) + 1/n*(f(n-1) + 1)
Expand and collect terms to get:
f(n) = f(n-1) + 1/n
And f(1) = 0. So:
f(1) = 0
f(2) = 0 + 1/2
f(3) = 0 + 1/2 + 1/3
f(4) = 0 + 1/2 + 1/3 + 1/4
That is, f(n) is the n_th "Harmonic number", which you can get in closed form only approximately. (Well, one less than the n_th Harmonic number. The problem would be prettier if you initialized max
to INT_MIN
and just let the loop run, so that f(1) = 1.)
The above is not a rigorous proof, since I was sloppy about expected values versus actual values. But I believe the answer is right anyway :-).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With