3 ms·
O(1) /extra/ space, but we must have working space at least the size of the output.
by debatem1 7y ago
O(1) /extra/ space, but we must have working space at least the size of the output.
- dmurray 7y agoThe 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.