5 ms·

> Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n). I think you oversimplified in the other directi

> Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n). I think you oversimplified in the other direction? An algorithm can make 1 pass over data (say it's n bits), then flip through all possible states of those n bits, taking exponential time. Or if you consider that to violate having a "fixed" upper bound (not sure this is meaningful in any useful sense, especially given it would probably need at least log(n) bits to know how far it's read its input), consider that it can even loop infinitely if it wants to.

selcuka 4y ago
> flip through all possible states of those n bits How do you do that in one pass?
- dataflow 4y ago
  By not reading the input again and just keeping the n-bit counter in unrelated memory, since the actual input is kind of irrelevant for this, only its size. Again, may or may not apply depending on what precisely they meant by a "fixed" additional amount of memory...
- fdupress 4y ago
  Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).
CJefferson 4y ago
Many stream-based compressors don't track how far they have read into their input, they just keep reading bytes, and writing out bytes. Things like zlib can be set up with a fixed sized buffer, and don't go allocating extra memory, so they definately can't start using arbitary extra space. You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.
aardvark179 4y ago
If it has a fixed upper bound on memory usage then it can’t store all the input to iterate through all the possible bit patterns, at least not for arbitrarily large inputs.
- HelloNurse 4y ago
  And trying an exponential number of candidate solutions cannot be considered "streaming" through the input: the algorithm doesn't make any real decision until the end is reached. Compare with algorithms that would like to be omniscient but make decisions at every step in order to produce streaming output and/or to forget old state and old inputs, like Viterbi decoding.

selcuka 4y ago

> flip through all possible states of those n bits How do you do that in one pass?

dataflow 4y ago
By not reading the input again and just keeping the n-bit counter in unrelated memory, since the actual input is kind of irrelevant for this, only its size. Again, may or may not apply depending on what precisely they meant by a "fixed" additional amount of memory...
fdupress 4y ago
Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).

CJefferson 4y ago

Many stream-based compressors don't track how far they have read into their input, they just keep reading bytes, and writing out bytes. Things like zlib can be set up with a fixed sized buffer, and don't go allocating extra memory, so they definately can't start using arbitary extra space. You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.

aardvark179 4y ago

If it has a fixed upper bound on memory usage then it can’t store all the input to iterate through all the possible bit patterns, at least not for arbitrarily large inputs.

HelloNurse 4y ago
And trying an exponential number of candidate solutions cannot be considered "streaming" through the input: the algorithm doesn't make any real decision until the end is reached. Compare with algorithms that would like to be omniscient but make decisions at every step in order to produce streaming output and/or to forget old state and old inputs, like Viterbi decoding.