4
$\begingroup$

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint?

A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to find the index, $i$, of the tallest person in the room. We have one variable for saving that index, which is updated when we see a person who is taller than the maximum height so far. We want to calculate the average number of times our variable is updated. For simplicity, assume that $p$ is a permutation of $\{1, 2, \dotsc, n\}$

Short answer: it is close to $\ln n$. (i.e: natural logarithm)

How can one solve such a question?

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – Juho Mar 28 '15 at 8:58
  • $\begingroup$ @Juho, it's high level contest question recently. $\endgroup$ – Anjela Minoeu Mar 28 '15 at 9:03
  • 1
    $\begingroup$ Does that mean you automatically put your hands up, and don't even try anything? $\endgroup$ – Juho Mar 28 '15 at 9:17
  • $\begingroup$ @Juho, No, I read the Hiring Problem on CLRS, It's closed but i couldent get it. please be kind :) $\endgroup$ – Anjela Minoeu Mar 28 '15 at 9:19
  • $\begingroup$ This being the case we need to know something about how the heights of people are distributed. $\endgroup$ – Jake Mar 28 '15 at 18:55
4
$\begingroup$

Let $T(n)$ denote the total number of updates to the variable when $n$ people have entered the room. For example, with $n=3$ there will be $3!=6$ possible orders where the heights are $1, 2, 3$. Notice that once the height 3 person enters, no further updates will occur, so let's group the six possible arrangements by when the height 3 person enters: $$\begin{array}{ccc} \mathbf{3}21 & \mathbf{3}12 \\ 1\mathbf{3}2 & 2\mathbf{3}1 \\ 12\mathbf{3} & 21\mathbf{3} \\ \end{array}$$ For each of these arrangements, let's count the number of updates we have to make before we see the tallest person. In the two arrangements where the height-3 person arrives first, there are 0 earlier updates. In the second row above, there will be 1 update we have to make before the tallest person arrives and in the third row there will be either 1 or two updates before the tallest person arrives: arrangement $12\mathbf{3}$ will require 2 updates (one for the height-1 person and another for the height-2 person and the arrangement $21\mathbf{3}$ will require 1 update, for the height-2 person. In this $n=3$ case, then, we'll have $0+2+3$ total prior updates (0 in row 1, 2 in row 2, and 3 in row 3). To this add the $3!=6$ updates for the tallest person, giving us a total $T(3)=5+6=11$.

Now let's look at the general case for $n$ people. As we did above, let's group the $n!$ possible arrangements by when the height-$n$ person arrived. Denote this tallest person by $X$ and the rest of the people by dots. As we did above, we'll defer counting the last update until later.

We'll have these possibilities, each of which can happen in $(n-1)!$ ways: $$\begin{array}{cc} \text{arrival of }X & \text{arrangement}\\ 1 & X\circ\dotsc\circ \\ 2 & \circ X\circ\dotsc\circ \\ 3 & \circ\circ X\circ\dotsc\circ\\ \dotsm & \dotsm \\ n & \circ\dotsc\circ X \end{array}$$

For each row above we'll count the total updates before the tallest person arrives: Obviously if the tallest person arrives first, we'll have no prior updates, so the first row above will give a total count of 0. Each of the following rows will look like this: $$ \underbrace{\circ\dotsc\circ}_k\ X\ \underbrace{\circ\dotsc\circ}_{n-1-k} $$ The first set of $k$ dots can be filled with the heights $\{1, 2, \dotsc, n-1\}$ and there are $\binom{n-1}{k}$ ways to choose these sets, each of which will contribute $T(k)$ updates. The last set of $n-1-k$ dots can be filled with the remaining numbers in $(n-1-k)!$ ways. Thus each row in the table will contribute $$ \binom{n-1}{k}T(k)(n-1-k)! $$ to the total of prior updates. Adding these and including the $n!$ updates for the tallest person we have the recurrence relation $$\begin{align} T(n) &= n! + \sum_{k=1}^{n-1}\binom{n-1}{k}T(k)(n-1-k)!\\ &= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!(n-1-k)!}T(k)(n-1-k)!\\ &= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!}T(k)\\ &= n!+ (n-1)!\sum_{k=1}^{n-1}\frac{T(k)}{k!}\\ \end{align}$$ Divide both sides by $n!$ to get $$ \frac{T(n)}{n!} = 1 + \frac{1}{n}\sum_{k=1}^{n-1}\frac{T(k)}{k!} $$ and remember that the average number of updates, $U(n)=T(n)/n!$ which gives us. $$ U(n) = 1 + \frac{1}{n}\sum_{k=1}^{n-1}U(k) $$ Now we'll find a simple closed form for this: $$\begin{align} U(n) &= 1+\frac{1}{n}\sum_{k=1}^{n-1}U(k)\\ &= 1+\frac{1}{n}\left(\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1) &\text{pulling out the last term}\\ &= 1+\frac{n-1}{n}\left(\frac{1}{n-1}\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1)\\ &= 1+\frac{n-1}{n}(U(n-1)-1)+\frac{1}{n}U(n-1) & \text{definition of }U(n-1)\\ &= U(n-1)\left(\frac{n-1}{n}+\frac{1}{n}\right)+\left(1-\frac{n-1}{n}\right)\\ &= U(n-1) + \frac{1}{n} \end{align}$$ Whaddya know? With $U(0)=0$ we just have $$ U(n) = 1 + \frac{1}{2}+\frac{1}{3}+\dotsm+\frac{1}{n} = H(n) $$ the $n$-th harmonic number, as it's known and it's also known that $H(n)$ is asymptotic to $\ln 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.