11

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.

2
  • I don't get it, you're not swapping anything only counting the number of times a new maximum has been found. How is this of help to you? What about the array {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}?
    – James
    Jul 18, 2011 at 16:07
  • Changed the word "Swaps" to "Assignments" in the title; should have written the title after I wrote out the question.
    – Dean J
    Jul 18, 2011 at 16:13

4 Answers 4

17

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 :-).

3
  • Setting up max as INT_MIN shouldn't be a problem. Thanks!
    – Dean J
    Jul 18, 2011 at 16:12
  • 3
    I tried with 10 million repetitions over a randomly sorted array of 20 elements. The result was ~3.597. The 20th harmonic number is ~3.5977. It would seem this answer is correct! Jul 18, 2011 at 16:34
  • 1
    Harmonic number has a closed form using Stirling numbers if that counts.
    – sdcvvc
    Jul 19, 2011 at 13:39
17

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

1
  • 1
    +1 for a nice simplification. Hopefully we can get you up to "commenting privileges" soon :-).
    – Nemo
    Jul 18, 2011 at 16:58
1

You can actually take this analysis a step further when the value of each item comes from a finite set. Let E(N, M) be the expected number of assignments when finding the max of N elements that come uniformly from an alphabet of size M. Then we can say...

E(0, M) = E(N, 0) = 0
E(N, M) = 1 + SUM[SUM[E(j, i) * (N - 1 Choose j) * ((M - i) / M)^(N-j-1) * (i / M) ^ j : j from 0 to N - 1] : i from 0 to M - 1]

This is a bit hard to come up with a closed form for but we can be sure that E(N, M) is in O(log(min(N, M))). This is because E(N, INF) is in THETA(log(N)) as the harmonic series sum grows proportional to the log function and E(N, M) < E(N, M + 1). Likewise when M < N we have E(N, M) < E(M, INF) as there is at M unique values.

And here's some code to compute E(N, M) yourself. I wonder if anyone can get this to a closed form?

#define N 100
#define M 100

double NCR[N + 1][M + 1];
double E[N + 1][M + 1];

int main() {
  NCR[0][0] = 1;
  for(int i = 1; i <= N; i++) {
    NCR[i][0] = NCR[i][i] = 1;
    for(int j = 1; j < i; j++) {
      NCR[i][j] = NCR[i - 1][j - 1] + NCR[i - 1][j];
    }
  }

  for(int n = 1; n <= N; n++) {
    for(int m = 1; m <= M; m++) {
      E[n][m] = 1;
      for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
          E[n][m] += NCR[n - 1][j] *
                     pow(1.0 * (m - i) / m, n - j - 1) *
                     pow(1.0 * i / m, j) * E[j][i] / m;
        }
      }
    }
  }
  cout << E[N][M] << endl;
}
1
  • it doesn't matter what set they come from, because as long as they are well-ordered it's the same as if they were the numbers 1 to n. So the answer is still the harmonic series.
    – Cam
    Jan 15, 2013 at 1:52
0

I am assuming all elements are distinct and counting the initial assignment to max outside the for loop.

If the array is sorted in increasing order, the variable max gets assigned to exactly n times (each time it gets a greater value).

If the array is sorted in decreasing order, the variable max gets assigned to exactly once (it gets assigned the first time and all subsequent values are smaller).

Edit: My formulation for a randomly permuted array was actually wrong, as pointed out in the comments. I think @Nemo posts the correct answer to this.

I think just counting the number of assignments is not really a true measure of the cost of this function. whether or not we actually update the value of max, we are actually comparing it exactly n times. So, fewer assignments does not really imply less work done.

Also observe that there are actually no swaps being done. Only assignments and comparisons.

3
  • Oh, cost is O(n), and a much better number to have in your head; this is to help a friend with their homework, and they were asked the question as stated, unfortunately.
    – Dean J
    Jul 18, 2011 at 16:18
  • I don't think this is really true. The probability is much more complex because you can't just say that "half the values will be greater", you also have to consider that they are also in random order. Yes on average half of the remaining items will be greater but if the remainder is sorted ascending the answer will be very different than if it was sorted descending. Jul 18, 2011 at 16:25
  • A trial of 10 million runs with 20 unique numbers randomly sorted yields an average count of ~3.6, not the ~9 your answer would suggest. Jul 18, 2011 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.