1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Also, "computing the average-case (...)" of what? Running time? This algorithm asymptotically runs in $\Theta (len(L))$, which is independent of the number of times max is assigned. $\endgroup$ – Auberon Apr 11 '16 at 0:36
  • $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Apr 11 '16 at 10:15
  • $\begingroup$ @Auberon The sentence reads to me as if the task is to compute the expected number of assignments to max. $\endgroup$ – Raphael Apr 11 '16 at 10:16
  • 2
    $\begingroup$ What is the input space and distribution? The results will depend on that. (You'll note that the two existing answers only apply to uniformly-random permutations.) $\endgroup$ – Raphael Apr 11 '16 at 10:17
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

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.