Every story and comment from the Hacker News API, in a layout borrowed from 2001.
A comment on Vitter's reservoir sampling algorithm D: randomly selecting unique items. Parent comment
We only need to consider values in the range 0 < k <= N/2. If k > N/2, we "pick the losers instead of winners" and that reduces k to that range.
The expected time E to pick k out of N, is N times the last k terms of H(N):
E(k) = N * (H(N) - H(N-k))
E(k) ~ N * (γ + ln(N) - γ - ln(N-k)) = N * (ln(N) - ln(N-k))
dE/dk ~ N/(N - k)
dE/dk <= 2
E(k) <= 2k
There are no comments on this comment yet.
We only need to consider values in the range 0 < k <= N/2. If k > N/2, we "pick the losers instead of winners" and that reduces k to that range.
The expected time E to pick k out of N, is N times the last k terms of H(N):
Applying the asymptote: We wish to determine its behavior as a function of k. Taking the derivative: which is positive and bounded above by 2 for 0 < k <= N/2: Using the fact that E(1) = 1, we have: So E cannot be worse than linear in k.