3 ms·
The paper describes an online one-pass algorithm for which this is not true: as you get each input value you accept or reject it. So you only need O(1) space to
by dmurray 7y ago
The paper describes an online one-pass algorithm for which this is not true: as you get each input value you accept or reject it. So you only need O(1) space to store the number of values you've seen, the number remaining, and the number you still need to accept.
- theelous3 7y agoThe number of values you've seen could be "only" an exabyte, which is a problem.
- thaumasiotes 7y agoYou're storing the number of values you've seen: So far, I've seen 172 values. You're not storing the values themselves. If the number of values you've processed is too large to fit in memory... you probably had to spend a long, long time processing those values. It's not a relevant objection.