Average-Case Analysis of a Simple Max-Finding Algorithm

Question

Given this piece of code:

FindMax(L):
   k = len(L) - 1
   max = L[k]
   k = k - 1
   while(k >= 0):
      if(L[k] > max):
         max = L[k]
      k = k - 1
   return max

How would you go about computing the average-case complexity with respect to the number of times $max$ is assigned? The way I've been taught to approach a question like this is to partition the sample space into events that could represent all possible inputs. But I'm having a hard time deciding what that partition should be

Answer 1

Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to form, he showed up with a wig and authentic 1960's attire. You can watch a recording of that lecture online if you're interested.

Another way to derive this result is to use indicator variables. Let $X_i$ be an indicator variable that is 1 if the value of max changes on the iteration of the loop corresponding to a length-$i$ subarray and 0 otherwise. Assuming the permutation given as input is uniformly random, this variable is 1 with probability $\frac{1}{i}$ because max only changes if the inspected element is the largest of its group. Using linearity of expectation, you can use this to show that the number of updates on expectation is $\Theta(\log n)$. Knuth's talk gives a different perspective using generating functions and derives a precise value as well as the variance.

Answer 2

The number of times that max is assigned to is known as the number of records (or left-to-right maxima) in the permutation. The following results are standard, and can be found in a paper of Kortchemski, which gives a much more refined analysis.

Lemma 1. Let $X_1,\ldots,X_n$ be indicator variables for the events that the $i$th element of a random permutation is a record (larger than all previous elements). Then $\Pr[X_i=1] = 1/i$ and the $X_i$ are independent.

Corollary. The expected number of records is $H_n = \log n + \gamma + O(1/n)$ (the $n$th harmonic number).

This follows from linearity of expectation.

Lemma 2. The generating function for the number of records is $$ T_n(q) = q(q+1)\cdots(q+n-1). $$ The coefficient $c(n,k)$ of $q^k$, which equals the number of permutations in $S_n$ having $k$ records, is the $(n,k)$ Stirling number of the first kind.

Corollary. The variance of the number of records is $\log n + \gamma - \pi^2/6 + O(1/n)$.

Indeed, notice that $T''_n(1) = \sum_k k(k-1) c(n,k)$. On the other hand, $$ T''_n(q) = \sum_{0 \leq i \neq j \leq n-1} \frac{T_n(q)}{(q+i)(q+j)}, $$ and substituting $q = 1$, $$ \frac{T''_n(1)}{n!} = \sum_{1 \leq i \neq j \leq n} \frac{1}{ij} = H_n^2 - \sum_{i=1}^n \frac{1}{i^2}. $$ Denoting by $R$ the number of records, this is a formula for $\mathbb{E}[R(R-1)]$. Now $$ \mathbb{V}[R] = \mathbb{E}[R(R-1)] + \mathbb{E}[R] - \mathbb{E}^2[R] = H_n^2 - \sum_{i=1}^n \frac{1}{i^2} + H_n - H_n^2 = H_n - \sum_{i=1}^n \frac{1}{i^2}. $$ It is well-known that $\sum_{i=1}^\infty 1/i^2 = \pi^2/6$, and we can estimate $\sum_{i=n+1}^\infty \leq \int_n^\infty dx/x^2 = 1/n$. In particular, $$ \mathbb{V}[R] = H_n - \frac{\pi^2}{6} + O(1/n). $$

Answer 3

Let me add one possible way of solution. By $T$ we denote the number of max updatings.

Direct analysis of cases after using mathematical induction gives

$$T(n) = n \cdot T(n-1) + (n-1)!$$ and from here obtain expected value

$$\frac{ T(n)}{n!} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum_{i=1}^{n}\frac{1}{i} - 1 =\\ = \ln n + \gamma + \varepsilon_{n} -1 = \ln n +O(1)$$

where $\gamma$ is Euler–Mascheroni constant and $\varepsilon_{n} \sim \frac{1}{2n}, n\rightarrow \infty$.