A math puzzle and a better algorithm for top-K

What a complex way to get that result. Here’s a simpler way:

In a row of n persons sorted randomly, the tallest will be in any of the n places with equal probability. Now, add people to the row one by one:

- After adding the first person, the person added will have probability 1 of being the tallest.

- After adding the second person, the person added will have probability ½ of being the tallest.

- After adding the third person, the person added will have probability ⅓ of being the tallest.

- …

- After adding the n-th person, the person added will have probability 1/n of being the tallest..

The result of it being Σ(1/n) over 8 billion follows from that. Only then do you need higher math to get to ln(n)

(Nitpick: that’s all assuming all persons to be of different length, which is impossible in practice, as it would mean having to measure length at less than a nanometer precision. In practice, there will be less than a thousand different lengths. That may change the equation quite drastically)

A math puzzle, its relationship with the average case complexity of computing top-K using a min heap, and a simple algorithm that performs better.