1 comment

[ 4.3 ms ] story [ 8.5 ms ] thread
There's a missing line at the end

> and `(1/1 + 1/2 + 1/3 + 1/4 + ... + 1/(N-1) + 1/N)` converges to ln(N) as N grows, so the total number of purchases will be O(N * ln(N))

A logarithm is much easier to think about than the un-shrunk harmonic series.