# 2021 Dec Gold HILO

The official solution mentions for data generated uniformly, the expected number of LO and HI is O(logN) for each x. How to prove that?

Suppose that Bessie’s number is N+0.5 and Elsie’s permutation is p. Then the number of LOs is the expected number of i such that p_i=\max(p_1,p_2,\ldots,p_i), which occurs with probability i. So the expected number of LOs is H_N=\sum_{i=1}^N\frac{1}{i}=\Theta(\log N). In general, if Bessie’s number is n+0.5, then the expected number of LOs is H_n and the expected number of HIs is H_{N-n}.

2 Likes

Sir Did you talk any alphastar or starleague classes?