Hacker News Reader

Comment by dataflow | Hacker News Reader

> 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.

View on HN

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.

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.

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.

> flip through all possible states of those n bits

How do you do that in one pass?

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...

Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).

Reply on news.ycombinator.com