# Tallest Person Average Memory Updating?

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?

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

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