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;
}