1
$\begingroup$

Given the following algorithm for finding the second largest element in a vector:

2ndMAX(v): n = length of v largest = 0 second_largest = 0 for i in 1 to n: if v[i] > largest: second_largest = largest largest = v[i]: else if v[i] > second_largest: second_largest = v[i] return second_largest

How many assignments is the algorithm expected to make to second_largest?

I can see the asymptotic lower and upper bounds on the problem, but how can I approach this probabilistically and give the expected number of assignments?

For the maximum I suppose it is N/2 assignments; but for the 2nd largest I am getting confused. I am trying to divide the cases in: largest comes before second largest, so there are no more assignments past the second largest, but there may be before the largest and between the largest and second largest. But it gets complicated really quickly. I also tried some inductive analysis but couldn't get too far.

$\endgroup$
  • $\begingroup$ I'm not even sure that for maximum it is $N/2$. I think it is $\log_2 N$. $\endgroup$ – rus9384 Aug 28 '17 at 14:07
3
$\begingroup$

Let's assume for simplicity that $v$ is a random permutation of the numbers $1,\ldots,n$. In step $i$, largest is assigned to if $v_i$ is the maximal element among $v_1,\ldots,v_i$ (a "record"), and second_largest is assigned to if $v_i$ is the second maximal element among $v_1,\ldots,v_i$. The probability of each of these events is $1/i$ (the second, assuming that $i \geq 2$), since $v_1,\ldots,v_i$ is a random permutation of $\{1,\ldots,i\}$.

Linearity of expectation shows that the expected number of times that largest is assigned to is $$ \sum_{i=1}^n \frac{1}{i} = H_n = \log n + \gamma + O\left(\frac{1}{n}\right). $$ Similarly, the expected number of times that second_largest is assigned to is $$ \sum_{i=2}^n \frac{1}{i} = H_n - 1 = \log n + \gamma - 1 + O\left(\frac{1}{n}\right). $$ In both formulas, $H_n$ is the $n$th harmonic number, $\log$ is the natural logarithm, and $\gamma$ is Euler's constant.

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