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?