3 ms·

If this really was such an obscure but useful algorithm, someone should change the title of this post to help people find it in the future so it doesn't remain

• LolWolf 7y ago
  It's... not that useful, as far as I can tell (unless I'm still under-caffeinated!) @avip mentions the following comment https://news.ycombinator.com/item?id=20961320 https://news.ycombinator.com/item?id=20961320 , which means that we only have to consider k ~ cn for 0 ≤ c ≤ 1/2. Drawing in this fashion, we have an expected runtime of k * (H_n - H_{(1-c)n}) ≤ k * (H_n - H_{n/2}) ~ O(k).[1] The latter is true since H_n ~ log n + C + O(1/n) for some[2] constant C. Of course, depending on what the author's constraints are, there would be an additional O(k) space requirement for keeping track of indices that have already been picked. Vitter's algorithm is particularly nice, since it can report the items without this additional space requirement. --- [1] https://en.wikipedia.org/wiki/Coupon_collector's_problem https://en.wikipedia.org/wiki/Coupon_collector's_problem [2] https://en.wikipedia.org/wiki/Euler–Mascheroni_constant https://en.wikipedia.org/wiki/Euler–Mascheroni_constant