Number of assignments necessary to find the minimum value in an array?

Viewed 4083

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.

4 Answers
Related