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 , 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.
@avip mentions the following comment 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
[2] https://en.wikipedia.org/wiki/Euler–Mascheroni_constant